Geometric Clustering to Minimize the Sum of Cluster Sizes

Vittorio Bilò, Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos

Abstract

We study geometric versions of the min-size k -clustering problem, a clustering problem which generalizes clustering to minimize the sum of cluster radii and has important applications. We prove that the problem can be solved in polynomial time when the points to be clustered are located on a line. For Euclidean spaces of higher dimensions, we show that the problem is NP-hard and present polynomial time approximation schemes. The latter result yields an improved approximation algorithm for the related problem of k-clustering to minimize the sum of cluster diameters.
BibTeX
@inproceedings{bilo2005geometric,
  author = {Vittorio Bilò and Ioannis Caragiannis and Christos Kaklamanis and Panagiotis Kanellopoulos},
  title = {{Geometric Clustering to Minimize the Sum of Cluster Sizes}},
  booktitle = {ESA},
  year = {2005},
  doi = {10.1007/11561071\_42},
}

Loading related content...

Figure