Authors: Babak Behsaz Mohammad R Salavatipour
Publish Date: 2014/07/04
Volume: 73, Issue: 1, Pages: 143-165
Abstract
Given a metric Vd and an integer k we consider the problem of partitioning the points of V into 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 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 3504 and 7008 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 frac32approximation 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 k 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 k have both ratio 2We would like to thank two anonymous referees for their great comments and suggestions especially for bringing to our attention the connection of Lemma 8 and 7 Babak Behsaz Supported in part by Alberta Innovates Graduate Student Scholarship Mohammad R Salavatipour Supported by NSERC and an Alberta Ingenuity New Faculty Award
Keywords: