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. 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 which also applies when the distance function is asymmetric. 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.