ECCC-Report TR02-025https://eccc.weizmann.ac.il/report/2002/025Comments and Revisions published for TR02-025en-usSun, 28 Apr 2002 14:39:43 +0300
Paper TR02-025
| Polynomial Time Approximation Schemes for Metric Min-Sum Clustering |
Wenceslas Fernandez de la Vega,
Marek Karpinski,
Claire Kenyon,
Yuval Rabani
https://eccc.weizmann.ac.il/report/2002/025We give polynomial time approximation schemes for the problem
of partitioning an input set of n points into a fixed number
k of clusters so as to minimize the sum over all clusters of
the total pairwise distances in a cluster. Our algorithms work
for arbitrary metric spaces as well as for points in d-dimensional space
where the distance between two points x,y is measured by
the square of the Euclidian distance (notice that
this is not a metric). Our algorithms
can be modified to handle other objective functions, such as minimizing the sum
over all clusters of the total distance to the best choice for
cluster center.
Sun, 28 Apr 2002 14:39:43 +0300https://eccc.weizmann.ac.il/report/2002/025