Next: MINIMUM K-SUPPLIER Up: Miscellaneous Previous: MINIMUM K-CLUSTERING Index

### MINIMUM K-CLUSTERING SUM

- 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 sum of all distances between elements in the same subset, i.e.,

- Good News: Approximable within 2 [200].

- Comment: If the triangle inequality is not satisfied the problem is called MINIMUM EDGE DELETION K-PARTITION. Approximable within 1.7 for k=2 [200]. The maximization variation in which the subsets C1,...,Ck 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 [148] Moreover, if d does not satisfy the triangle inequality then the bounds are c-1 and c, respectively [148]; the cases c=3 and c=4 are approximable within 2 [147]. Finally, if required sizes c1,...,ck of the subsets are given and the triangle inequality is satisfied then the maximization problem is approximable within [222].

Next: MINIMUM K-SUPPLIER Up: Miscellaneous Previous: MINIMUM K-CLUSTERING Index