DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2022.56

Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters

Authors: Zachary Friggstad and Mahya Jamshidian

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract

We give an improved approximation algorithm for two related clustering problems. In the Minimum Sum of Radii clustering problem (MSR), we are to select k balls in a metric space to cover all points while minimizing the sum of the radii of these balls. In the Minimum Sum of Diameters clustering problem (MSD), we are to simply partition the points of a metric space into k parts while minimizing the sum of the diameters of these parts. We present a 3.389-approximation for MSR and a 6.546-approximation for MSD, improving over their respective 3.504 and 7.008 approximations developed by Charikar and Panigrahy (2001). In particular, our guarantee for MSD is better than twice our guarantee for MSR. Our approach refines a so-called bipoint rounding procedure of Charikar and Panigrahy’s algorithm by considering centering balls at some points that were not necessarily centers in the bipoint solution. This added versatility enables the analysis of our improved approximation guarantees. We also provide an alternative approach to finding the bipoint solution using a straightforward LP rounding procedure rather than a primal-dual algorithm.

Cite as

Zachary Friggstad and Mahya Jamshidian. Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{friggstad_et_al:LIPIcs.ESA.2022.56,
  author =	{Friggstad, Zachary and Jamshidian, Mahya},
  title =	{{Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.56},
  URN =		{urn:nbn:de:0030-drops-169946},
  doi =		{10.4230/LIPIcs.ESA.2022.56},
  annote =	{Keywords: Approximation Algorithms, Clustering, Linear Programming}
}

Search Results

Documents authored by Jamshidian, Mahya

Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters

Abstract

Cite as

Thanks for your feedback!

Could not send message