MINIMUM K-CLUSTERING SUM

• 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 sum of all distances between elements in the same subset, i.e.,
  
  $$\displaystyle\sum\limits_{i=1}^{k} \displaystyle\sum\limits_{v_1,v_2\in C_i} d(v_1,v_2).$$
  
  

  
  

• Good News: Approximable within 2 [213].

• Comment: If the triangle inequality is not satisfied the problem is called MINIMUM EDGE DELETION K-PARTITION. Approximable within 1.7 for k=2 [213]. The maximization variation in which the subsets $C_1,...,C_k$ must be of equal size c is approximable within 2(c-1)/c or (c+1)/c, depending on whether c is even or odd [160] Moreover, if d does not satisfy the triangle inequality then the bounds are c-1 and c, respectively [160]; the cases c=3 and c=4 are approximable within 2 [159]. Finally, if required sizes $c_1,...,c_k$ of the subsets are given and the triangle inequality is satisfied then the maximization problem is approximable within $2\sqrt 2$ [239].