- 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 [202] and [254].*Bad News:*Not approximable within 2 for any [202] and [254].*Comment:*The same positive and negative results are valid for the geometric (Euclidean)*k*-clustering problem in 3 dimensions [202] and for rectilinear*k*-clustering problem in 2 dimensions. The geometric*k*-clustering problem in 2 dimensions is not approximable within 1.969 [152]. Other variants are also studied in this paper.*Garey and Johnson:*MS9