Document Open Access Logo

Capacitated Sum-Of-Radii Clustering: An FPT Approximation

Authors Tanmay Inamdar, Kasturi Varadarajan

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.62.pdf
  • Filesize: 0.53 MB
  • 17 pages

Document Identifiers

Author Details

Tanmay Inamdar
  • Department of Computer Science, University of Iowa, Iowa City, IA, USA
Kasturi Varadarajan
  • Department of Computer Science, University of Iowa, Iowa City, IA, USA

Funding

This research is partially supported by the National Science Foundation under Grant CCF-1615845.

Cite As Get BibTex

Tanmay Inamdar and Kasturi Varadarajan. Capacitated Sum-Of-Radii Clustering: An FPT Approximation. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 62:1-62:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.62

Abstract

In sum of radii clustering, the input consists of a finite set of points in a metric space. The problem asks to place a set of k balls centered at a subset of the points such that every point is covered by some ball, and the objective is to minimize the sum of radii of these balls. In the capacitated version of the problem, we want to assign each point to a ball containing it, such that no ball is assigned more than U points, where U denotes the capacity of the points. While constant approximations are known for the uncapacitated version of the problem, there is no work on the capacitated version. We make progress on this problem by obtaining a constant approximation using a Fixed Parameter Tractable (FPT) algorithm. In particular, the running time of the algorithm is of the form 2^O(k²) ⋅ n^O(1). As a warm-up for this result, we also give a constant approximation for the uncapacitated sum of radii clustering problem with matroid constraints, thus obtaining the first FPT approximation for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
Keywords
  • Sum-of-radii Clustering
  • Capacitated Clustering

Metrics

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

References

  1. Marek Adamczyk, Jaroslaw Byrka, Jan Marcinkowski, Syed M. Meesum, and Michal Wlodarczyk. Constant-factor FPT approximation for capacitated k-median. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany., pages 1:1-1:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.1.
  2. Hyung-Chan An, Mohit Singh, and Ola Svensson. Lp-based algorithms for capacitated facility location. SIAM J. Comput., 46(1):272-306, 2017. URL: https://doi.org/10.1137/151002320.
  3. Sayan Bandyapadhyay, Santanu Bhowmick, Tanmay Inamdar, and Kasturi R. Varadarajan. Capacitated covering problems in geometric spaces. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry, SoCG 2018, June 11-14, 2018, Budapest, Hungary, volume 99 of LIPIcs, pages 7:1-7:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.7.
  4. Babak Behsaz and Mohammad R. Salavatipour. On minimum sum of radii and diameters clustering. Algorithmica, 73(1):143-165, 2015. URL: https://doi.org/10.1007/s00453-014-9907-3.
  5. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Trans. Algorithms, 13(2):23:1-23:31, 2017. Google Scholar
  6. Jaroslaw Byrka, Bartosz Rybicki, and Sumedha Uniyal. An approximation algorithm for uniform capacitated k-median problem with 1+ε 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. URL: https://doi.org/10.1007/978-3-319-33461-5_22.
  7. 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. URL: https://doi.org/10.1006/jcss.2002.1882.
  8. 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.
  9. Danny Z Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Algorithmica, 75(1):27-52, 2016. Google Scholar
  10. 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. URL: http://dl.acm.org/citation.cfm?id=1070432.1070569.
  11. 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, July 9-12, 2019, Patras, Greece., pages 41:1-41:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.41.
  12. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  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: https://doi.org/10.4230/LIPIcs.ICALP.2016.73.
  14. 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.
  15. Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  16. MohammadTaghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz. Budgeted red-blue median and its generalizations. In European Symposium on Algorithms, pages 314-325. Springer, 2010. Google Scholar
  17. Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of operations research, 10(2):180-184, 1985. Google Scholar
  18. Samir Khuller and Yoram J Sussmann. The capacitated k-center problem. SIAM Journal on Discrete Mathematics, 13(3):403-418, 2000. Google Scholar
  19. Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep. Constant approximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 646-659, 2018. Google Scholar
  20. 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: https://doi.org/10.1137/1.9781611974331.ch56.
  21. Shi Li. On uniform capacitated k-median beyond the natural LP relaxation. ACM Trans. Algorithms, 13(2):22:1-22:18, 2017. URL: https://doi.org/10.1145/2983633.
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 About DROPS Imprint Privacy Contact