Next: MINIMUM K-CLUSTERING SUM
Previous: MINIMUM K-CENTER
Finite set X, a distance
for each pair .
The distances must satisfy the triangle inequality.
A partition of X into disjoint subsets
The largest distance between two elements in the same subset, i.e.,
- Good News:
Approximable within 2  and .
- Bad News:
Not approximable within 2
 and .
The same positive and negative results are valid for
the geometric (Euclidean) k-clustering problem in 3
and for rectilinear k-clustering problem in 2 dimensions.
The geometric k-clustering problem in 2 dimensions is not
approximable within 1.969 .
Other variants are also studied in this paper.
- Garey and Johnson: MS9