Document Open Access Logo

On the Fixed-Parameter Tractability of Capacitated Clustering

Authors Vincent Cohen-Addad, Jason Li

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.41.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

Vincent Cohen-Addad
  • CNRS & Sorbonne Université, Paris, France
Jason Li
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Cohen-Addad, Vincent: Ce projet a bénéficié d'une aide de l'Etat gérée par l'Agence Nationale de la Recherche au titre du Programme Appel à projets générique JCJC 2018 portant la référence suivante: ANR-18-CE40-0004-01.
  • Li, Jason: Supported in part by NSF awards CCF-1536002, CCF-1540541, and CCF-1617790.

Cite AsGet BibTex

Vincent Cohen-Addad and Jason Li. On the Fixed-Parameter Tractability of Capacitated Clustering. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.41

Abstract

We study the complexity of the classic capacitated k-median and k-means problems parameterized by the number of centers, k. These problems are notoriously difficult since the best known approximation bound for high dimensional Euclidean space and general metric space is Theta(log k) and it remains a major open problem whether a constant factor exists. We show that there exists a (3+epsilon)-approximation algorithm for the capacitated k-median and a (9+epsilon)-approximation algorithm for the capacitated k-means problem in general metric spaces whose running times are f(epsilon,k) n^{O(1)}. For Euclidean inputs of arbitrary dimension, we give a (1+epsilon)-approximation algorithm for both problems with a similar running time. This is a significant improvement over the (7+epsilon)-approximation of Adamczyk et al. for k-median in general metric spaces and the (69+epsilon)-approximation of Xu et al. for Euclidean k-means.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
  • Theory of computation → Fixed parameter tractability
  • Mathematics of computing → Probabilistic algorithms
  • Mathematics of computing → Dimensionality reduction
Keywords
  • approximation algorithms
  • fixed-parameter tractability
  • capacitated
  • k-median
  • k-means
  • clustering
  • core-sets
  • Euclidean

Metrics

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

References

  1. M. Adamczyk, J. Byrka, J. Marcinkowski, S. M. Meesum, and M. Włodarczyk. Constant factor FPT approximation for capacitated k-median. ArXiv e-prints, September 2018. URL: http://arxiv.org/abs/1809.05791.
  2. Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation Schemes for Euclidean k-Medians and Related Problems. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 106-113, 1998. URL: http://dx.doi.org/10.1145/276698.276718.
  3. Jarosław Byrka, Krzysztof Fleszar, Bartosz Rybicki, and Joachim Spoerhase. Bi-factor approximation algorithms for hard capacitated k-median problems. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 722-736. SIAM, 2014. Google Scholar
  4. Jarosław Byrka, Bartosz Rybicki, and Sumedha Uniyal. An Approximation Algorithm for Uniform Capacitated k-Median Problem with 1+ε Capacity Violation. In International Conference on Integer Programming and Combinatorial Optimization, pages 262-274. Springer, 2016. Google Scholar
  5. Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k-Median. In STOC, volume 98, pages 114-123. Citeseer, 1998. Google Scholar
  6. Moses Charikar, Sudipto Guha, Éva Tardos, and David 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. K. Chen. On Coresets for k-Median and k-Means Clustering in Metric and ELuclidean Spaces and Their Applications. SIAM Journal on Computing, 39(3):923-947, 2009. Google Scholar
  8. 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 '05, pages 952-958, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.
  9. Vincent Cohen-Addad. Approximation Schemes for Capacitated Clustering in Doubling Metrics. CoRR, abs/1812.07721, 2018. URL: http://arxiv.org/abs/1812.07721.
  10. Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The Bane of Low-Dimensionality Clustering. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 441-456, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.30.
  11. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In ICALP 2019, 2019. Google Scholar
  12. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In Lawrence L. Larmore and Michel X. Goemans, editors, Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 50-58. ACM, 2003. URL: http://dx.doi.org/10.1145/780542.780550.
  13. 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. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.73.
  14. G. Frahling and C. Sohler. Coresets in dynamic geometric data streams. In STOC, pages 209-217, 2005. Google Scholar
  15. 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, SODA '18, pages 2821-2837, Philadelphia, PA, USA, 2018. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3174304.3175483.
  16. Anupam Gupta, Euiwoong Lee, Jason Li, Pasin Manurangsi, and Michal Wlodarczyk. Losing Treewidth by Separating Subsets. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1731-1749, 2019. URL: http://dx.doi.org/10.1137/1.9781611975482.104.
  17. Sariel Har-Peled and Akash Kushal. Smaller Coresets for k-Median and k-Means Clustering. Discrete & Computational Geometry, 37(1):3-19, 2007. URL: http://dx.doi.org/10.1007/s00454-006-1271-x.
  18. Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, pages 291-300, 2004. URL: http://dx.doi.org/10.1145/1007352.1007400.
  19. Amit Kumar, Yogish Sabharwal, and Sandeep Sen. A Simple Linear Time (1+ ") -Approximation Algorithm for k-Means Clustering in Any Dimensions. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS '04, pages 454-462, Washington, DC, USA, 2004. IEEE Computer Society. URL: http://dx.doi.org/10.1109/FOCS.2004.7.
  20. Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2), 2010. URL: http://dx.doi.org/10.1145/1667053.1667054.
  21. Euiwoong Lee. Partitioning a graph into small pieces with applications to path transversal. Mathematical Programming, March 2018. URL: http://dx.doi.org/10.1007/s10107-018-1255-7.
  22. 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. URL: http://dx.doi.org/10.1137/1.9781611973730.47.
  23. Shi Li. Approximating capacitated k-median with (1 + k open facilities. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 786-796, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch56.
  24. Shi Li. On Uniform Capacitated k-Median Beyond the Natural LP Relaxation. ACM Trans. Algorithms, 13(2):22:1-22:18, 2017. URL: http://dx.doi.org/10.1145/2983633.
  25. Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 1088-1101, New York, NY, USA, 2018. ACM. URL: http://dx.doi.org/10.1145/3188745.3188828.
  26. Dániel Marx and Michal Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In Algorithms - ESA 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, pages 865-877, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_72.
  27. Shyam Narayanan and Jelani Nelson. Optimal terminal dimensionality reduction in Euclidean space. CoRR - To appear in the proceedings of STOC'19, abs/1810.09250, 2018. URL: http://arxiv.org/abs/1810.09250.
  28. Yicheng Xu, Yong Zhang, and Yifei Zou. A constant parameterized approximation for hard-capacitated k-means. CoRR, abs/1901.04628, 2019. URL: http://arxiv.org/abs/1901.04628.
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