Document Open Access Logo

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii

Authors Sayan Bandyapadhyay, William Lochet, Saket Saurabh

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2023.12.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Clustering
  • FPT-approximation

Metrics

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

Abstract

Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general metric into k clusters to minimize the sum of cluster radii, subject to non-uniform hard capacity constraints (Capacitated Sum of Radii ). In particular, we give a (15+ε)-approximation algorithm that runs in 2^𝒪(k²log k) ⋅ n³ time. 
When capacities are uniform, we obtain the following improved approximation bounds.
- A (4 + ε)-approximation with running time 2^𝒪(klog(k/ε)) n³, which significantly improves over the FPT 28-approximation of Inamdar and Varadarajan [ESA 2020].
- A (2 + ε)-approximation with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ and a (1+ε)-approxim- ation with running time 2^𝒪(kdlog ((k/ε))) n³ in the Euclidean space. Here d is the dimension. 
- A (1 + ε)-approximation in the Euclidean space with running time 2^𝒪(k/ε² ⋅log(k/ε)) dn³ if we are allowed to violate the capacities by (1 + ε)-factor. We complement this result by showing that there is no (1 + ε)-approximation algorithm running in time f(k)⋅ n^𝒪(1), if any capacity violation is not allowed.

Cite As Get BibTex

Sayan Bandyapadhyay, William Lochet, and Saket Saurabh. FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.SoCG.2023.12

Author Details

Sayan Bandyapadhyay
  • Department of Computer Science, Portland State University, OR, USA
William Lochet
  • LIRMM, Université de Montpellier, CNRS, Montpellier, France
Saket Saurabh
  • The Institute of Mathematical Sciences, HBNI, Chennai, India

Funding

  • Saurabh, Saket: Supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement no. 819416), and Swarnajayanti Fellowship (no. DST/SJF/MSA01/2017-18).

References

  1. Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed Mohammad Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 1:1-1:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.1.
  2. Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and euclidean k-median by primal-dual algorithms. SIAM Journal on Computing, 49(4):FOCS17-97, 2019. Google Scholar
  3. Hyung-Chan An, Aditya Bhaskara, Chandra Chekuri, Shalmoli Gupta, Vivek Madan, and Ola Svensson. Centrality of trees for capacitated k-center. Math. Program., 154(1-2):29-53, 2015. URL: https://doi.org/10.1007/s10107-014-0857-y.
  4. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004. Google Scholar
  5. Mihai Badoui, Sariel Har-Peled, and Piotr Indyk. Approximate clustering via core-sets. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, STOC '02, pages 250-257, New York, NY, USA, 2002. Association for Computing Machinery. URL: https://doi.org/10.1145/509907.509947.
  6. Judit Barilan, Guy Kortsarz, and David Peleg. How to allocate network centers. Journal of Algorithms, 15(3):385-415, 1993. Google Scholar
  7. Anup Bhattacharya, Ragesh Jaiswal, and Amit Kumar. Faster algorithms for the constrained k-means problem. Theory Comput. Syst., 62(1):93-115, 2018. URL: https://doi.org/10.1007/s00224-017-9820-7.
  8. Jaroslaw Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Piotr Indyk, editor, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 722-736. SIAM, 2015. Google Scholar
  9. Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 737-756. SIAM, 2014. Google Scholar
  10. Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+backslashepsilon capacity violation. In Quentin Louveaux and Martin Skutella, editors, Integer Programming and Combinatorial Optimization - 18th International Conference, IPCO 2016, Liège, Belgium, June 1-3, 2016, Proceedings, volume 9682 of Lecture Notes in Computer Science, pages 262-274. Springer, 2016. Google Scholar
  11. Moses Charikar, Sudipto Guha, Éva Tardos, and David B. Shmoys. A constant-factor approximation algorithm for the k-median problem. J. Comput. Syst. Sci., 65(1):129-149, 2002. Google Scholar
  12. Moses Charikar and Rina Panigrahy. Clustering to minimize the sum of cluster diameters. J. Comput. Syst. Sci., 68(2):417-441, 2004. URL: https://doi.org/10.1016/j.jcss.2003.07.014.
  13. Julia Chuzhoy and Yuval Rabani. Approximating k-median with non-uniform capacities. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 952-958. SIAM, 2005. Google Scholar
  14. Vincent Cohen-Addad. Approximation schemes for capacitated clustering in doubling metrics. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2241-2259. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.138.
  15. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight fpt approximations for k-median and k-means. arXiv preprint arXiv:1904.12334, 2019. Google Scholar
  16. Vincent Cohen-Addad and CS Karthik. Inapproximability of clustering in lp metrics. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 519-539. IEEE, 2019. Google Scholar
  17. Vincent Cohen-Addad, CS Karthik, and Euiwoong Lee. On approximability of clustering problems without candidate centers. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2635-2648. SIAM, 2021. Google Scholar
  18. Vincent Cohen-Addad and Euiwoong Lee. Johnson coverage hypothesis: Inapproximability of k-means and k-median in ?p-metrics. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1493-1530. SIAM, 2022. Google Scholar
  19. Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1-41:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.41.
  20. Marek Cygan, MohammadTaghi Hajiaghayi, and Samir Khuller. LP rounding for k-centers with non-uniform hard capacities. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 273-282. IEEE Computer Society, 2012. URL: https://doi.org/10.1109/FOCS.2012.63.
  21. H. Gökalp Demirci and Shi Li. Constant approximation for capacitated k-median with (1+epsilon)-capacity violation. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 73:1-73:14, 2016. Google Scholar
  22. Hu Ding and Jinhui Xu. A unified framework for clustering constrained data without locality property. Algorithmica, 82(4):808-852, 2020. URL: https://doi.org/10.1007/s00453-019-00616-2.
  23. Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On metric clustering to minimize the sum of radii. Algorithmica, 57(3):484-498, 2010. URL: https://doi.org/10.1007/s00453-009-9282-7.
  24. Matt Gibson, Gaurav Kanade, Erik Krohn, Imran A. Pirwani, and Kasturi R. Varadarajan. On clustering to minimize the sum of radii. SIAM J. Comput., 41(1):47-60, 2012. URL: https://doi.org/10.1137/100798144.
  25. Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  26. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of algorithms, 31(1):228-248, 1999. Google Scholar
  27. Anupam Gupta, Euiwoong Lee, and Jason Li. An fpt algorithm beating 2-approximation for k-cut. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2821-2837. SIAM, 2018. Google Scholar
  28. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michał Włodarczyk. Losing treewidth by separating subsets. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1731-1749. SIAM, 2019. Google Scholar
  29. Tanmay Inamdar and Kasturi R. Varadarajan. Capacitated sum-of-radii clustering: An FPT approximation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 62:1-62:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.62.
  30. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89-112, 2004. Google Scholar
  31. Samir Khuller and Yoram J. Sussmann. The capacitated K-center problem. SIAM J. Discret. Math., 13(3):403-418, 2000. URL: https://doi.org/10.1137/S0895480197329776.
  32. Euiwoong Lee. Partitioning a graph into small pieces with applications to path transversal. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1546-1558. SIAM, 2017. Google Scholar
  33. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 696-707, 2015. Google Scholar
  34. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithms, 13(2):22:1-22:18, 2017. Google Scholar
  35. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830, 2011. Google Scholar
  36. Michael Steinbach, George Karypis, and Vipin Kumar. A comparison of document clustering techniques. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining Workshop on Text Mining, pages 525-526, 2000. Google Scholar
  37. Yicheng Xu, Yong Zhang, and Yifei Zou. A constant parameterized approximation for hard-capacitated k-means. CoRR, abs/1901.04628, 2019. URL: https://arxiv.org/abs/1901.04628.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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