ND50 MINIMUM K-CLUSTERING SUM

Next: ND51 MINIMUM K-SUPPLIER Up: Miscellaneous Previous: ND49 MINIMUM K-CLUSTERING

I NSTANCE : Finite set X , a distance for each pair .
S OLUTION : A partition of X into disjoint subsets .
M EASURE : The sum of all distances between elements in the same subset, i.e.,
Bad News: Not in A PX [ 313 ].
Comment: Approximable within 1.7 for p=2 and within 2 for if d satisfies the triangle inequality [ 145 ].

Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997