Clustering to minimize the sum of cluster diameters

摘要

We study the problem of clustering points in a metric space so as to minimize the sum of cluster diameters or the sum of cluster radii. Significantly improving on previous results, we present a primal–dual based constant factor approximation algorithm for this problem. We present a simple greedy algorithm that achieves a logarithmic approximation. This also applies when the distance function is asymmetric and the objective is to minimize the sum of cluster radii. The previous best-known result obtained a logarithmic approximation with a constant factor blowup in the number of clusters. We also obtain an incremental clustering algorithm that maintains a solution whose cost is at most a constant factor times that of optimal with a constant factor blowup in the number of clusters.