1;3409;0c Approximating min-sum k-clustering in metric spaces

Approximating min-sum k-clustering in metric spaces

STOC 2001, 2001
Pages: 11-20DOI: 10.1145/380752.380754



The min-sum k-clustering problem in a metric space is to find a partition of the space into k clusters as to minimize the total sum of distances between pairs of points assigned to the same cluster. We give the first polynomial time non-trivial approximation algorithm for this problem. The algorithm provides an $ratio$ approximation to the min-sum k-clustering problem in general metric spaces, with running time $runtime$. The result is based on embedding of metric spaces into hierarchically separated trees. We also provide a bicriteria approximation result that provides a constant approximation factor solution with only a constant factor increase in the number of clusters. This result is obtained by modifying and drawing ideas from recently developed primal dual approximation algorithms for facility location.