Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-025 | 26th April 2002 00:00

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering



We 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.

ISSN 1433-8092 | Imprint