On Minimum Sum of Radii and Diameters Clustering

摘要

Given a metric and an integer , we consider the problem of partitioning the points of into at most clusters so as to minimize the sum of radii or the sum of diameters of these clusters. The former problem is called the minimum sum of radii (MSR) problem and the latter is the minimum sum of diameters (MSD) problem. The current best polynomial time algorithms for these problems have approximation ratios 3.504 and 7.008, respectively. We call a cluster containing a single point, a singleton cluster. For the MSR problem when singleton clusters are not allowed, we give an exact algorithm for metrics induced by unweighted graphs. In addition, we show that in this case, a solution consisting of the best single cluster for each connected component of the graph is a -approximation algorithm. For the MSD problem on the plane with Euclidean distances, we present a polynomial time approximation scheme. In addition, we settle the open problem of complexity of the MSD problem with constant by giving a polynomial time exact algorithm in this case. The previously best known approximation algorithms for MSD on the plane or for MSD with constant have both ratio 2.