Document Open Access Logo

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

Authors Zachary Friggstad, Mahya Jamshidian

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.56.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Zachary Friggstad
  • Department of Computing Science, University of Alberta, Edmonton, Canada
Mahya Jamshidian
  • Department of Computing Science, University of Alberta, Edmonton, Canada

Funding

  • Friggstad, Zachary: Supported by an NSERC Discovery Grant and Discovery Accelerator Supplement.

Acknowledgements

The first author would like to thank Mohammad R. Salavatipour for preliminary discussions on this problem.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ESA.2022.56

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Approximation Algorithms
  • Clustering
  • Linear Programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. N. Bansal, A. Chakrabarti, A. Epstein, and B. Schieber. A quasi-ptas for unsplittable flow on line graphs. In Proceedings of 38th Annual Symposium on Theory of Computing (STOC), STOC '06, pages 721-729, New York, NY, USA, 2006. Association for Computing Machinery. Google Scholar
  2. J. Batra, N. Garg, A. Kumar, T. Mömke, and A. Wiese. New approximation schemes for unsplittable flow on a path. In Proceedings of the 2015 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 47-58, 2015. Google Scholar
  3. B. Behsaz and M. R. Salavatipour. On minimum sum of radii and diameters clustering. Algorithmica, 73(1):143-165, September 2015. Google Scholar
  4. V. Capoyleas, G. Rote, and G. Woeginger. Geometric clusterings, 1990. Google Scholar
  5. M. Charikar and S. Guha. Improved combinatorial algorithms for the facility location and k-median problems. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 378-388, 1999. Google Scholar
  6. M. Charikar, S. Guha, É. Tardos, and D. B. Shmoys. A constant-factor approximation algorithm for the k-median problem. Journal of Computer and System Sciences, 65(1):129-149, 2002. Google Scholar
  7. M. Charikar and R. Panigrahy. Clustering to minimize the sum of cluster diameters. Journal of Computer and System Sciences, 68(2):417-441, 2004. Special Issue on STOC 2001. Google Scholar
  8. S. Doddi, M. V. Marathe, S. S. Ravi, D. S. Taylor, and P. Widmayer. Approximation algorithms for clustering to minimize the sum of diameters. In In Proceedings of 7th Scandanavian Workshop on Algorithm Theory (SWAT), pages 237-250. Springer-Verlag, 2000. Google Scholar
  9. M. E. Dyer and A. M. Frieze. A simple heuristic for the p-centre problem. Operations Research Letters, 3(6):285-288, 1985. Google Scholar
  10. M. Gibson, G. Kanade, E. Krohn, I. A. Pirwani, and K. Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484-498, February 2009. Google Scholar
  11. M. Gibson, G. Kanade, E. Krohn, I. A. Pirwani, and K. Varadarajan. On clustering to minimize the sum of radii. SIAM Journal on Computing, 41(1):47-60, 2012. Google Scholar
  12. F. Grandoni, T. Mömke, and A. Wiese. A ptas for unsplittable flow on a path. In To appear in proceedings of 54th ACM Symposium on Theory of Computing (STOC), 2022. Google Scholar
  13. F. Grandoni, T. Mömke, and A. Wiese. Unsplittable flow on a path: The game! In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 906-926, 2022. Google Scholar
  14. F. Grandoni, T. Mömke, A. Wiese, and A. Zhou. To augment or not to augment: Solving unsplittable flow on a path by creating slack. In Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2411-2422, 2017. Google Scholar
  15. F. Grandoni, T. Mömke, A. Wiese, and H. Zhou. A (5/3 + ε)-approximation for unsplittable flow on a path: Placing small tasks into boxes. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 607-619, New York, NY, USA, 2018. Association for Computing Machinery. Google Scholar
  16. P. Hansen and B. Jaumard. Minimum sum of diameters clustering. Journal of Classification, 4(2):215-226, September 1987. Google Scholar
  17. P. Heggernes and D. Lokshtanov. Optimal broadcast domination in polynomial time. Discrete Mathematics, 306(24):3267-3280, 2006. Google Scholar
  18. D. S. Hochbaum and D. B. Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-184, 1985. Google Scholar
  19. K. Jain and V. V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J. ACM, 48(2):274-296, March 2001. Google Scholar
  20. O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems. ii: The p-medians. SIAM Journal on Applied Mathematics, 37(3):539-560, 1979. Google Scholar
  21. J. H. Lin and J. S. Vitter. Approximation algorithms for geometric median problems. Information Processing Letters, 44(5):245-249, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact