On Minimum Sum of Radii and Diameters Clustering

摘要

Given a metric (V, d) and an integer k, we consider the problem of covering the points of V with at most k 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 Radii (MSR) problem and the latter is the Minimum Sum Diameters (MSD) problem. The current best polynomial time algorithms for these problems have approximation ratios 3.504 and 7.008, respectively [2]. For the MSR problem, we give an exact algorithm when the metric is the shortest-path metric of an unweighted graph and there cannot be any singleton clusters. For the MSD problem on the plane with Euclidean distances, we present a polynomial time approximation scheme.