Next: MINIMUM K-CLUSTERING SUM Up: Miscellaneous Previous: MINIMUM K-CENTER Index

### MINIMUM K-CLUSTERING

- INSTANCE: Finite set X, a distance for each pair . The distances must satisfy the triangle inequality.

- SOLUTION: A partition of X into disjoint subsets .

- MEASURE: The largest distance between two elements in the same subset, i.e., .

- Good News: Approximable within 2 [190] and [237].

- Bad News: Not approximable within 2 for any [190] and [237].

- Comment: The same positive and negative results are valid for the geometric (Euclidean) k-clustering problem in 3 dimensions [190] and for rectilinear k-clustering problem in 2 dimensions. The geometric k-clustering problem in 2 dimensions is not approximable within 1.969 [141]. Other variants are also studied in this paper.

- Garey and Johnson: MS9