MINIMUM K-CLUSTERING

• INSTANCE: Finite set X, a distance $d(x,y)\in N$ for each pair $x,y\in X$. The distances must satisfy the triangle inequality.

• SOLUTION: A partition of X into disjoint subsets $C_1,C_2,\ldots,C_k$.

• MEASURE: The largest distance between two elements in the same subset, i.e., $\max\limits_{i\in [1..k]\atop x,y\in C_i} d(x,y)$.

  
  

• Good News: Approximable within 2 [202] and [254].

• Bad News: Not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [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