Journal Title Title of Journal: Algorithmica Search In Journal Title: Abbravation: Algorithmica Search In Journal Abbravation: Publisher Springer US Search In Publisher: DOI 10.1002/nadc.200744278 Search In DOI: ISSN 1432-0541 Search In ISSN:
Search In Title Of Papers:

# On Minimum Sum of Radii and Diameters Clustering

## Abstract

Given a metric $$(V,d)$$ 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 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 $$\frac{3}{2}$$-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 $$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 2.We 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.

## References

.
Search In Abstract Of Papers:

##### Search Result:

Help video to use 'Paper Search Console'