Document Open Access Logo

Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs

Authors Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.33.pdf
  • Filesize: 0.75 MB
  • 14 pages

Document Identifiers

Author Details

Vincent Cohen-Addad
  • Sorbonne Université, CNRS, Laboratoire d'informatique de Paris 6, LIP6, F-75252 Paris, France
Marcin Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland

Funding

This work is a part of projects CUTACOMBS (Ma. Pilipczuk) and TOTAL (Mi. Pilipczuk) that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreements No. 714704 and No. 677651, respectively). Ce projet a bénéficié d'une aide de l'État 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.

Cite As Get BibTex

Vincent Cohen-Addad, Marcin Pilipczuk, and Michał Pilipczuk. Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ESA.2019.33

Abstract

We consider the k-Median problem on planar graphs: given an edge-weighted planar graph G, a set of clients C subseteq V(G), a set of facilities F subseteq V(G), and an integer parameter k, the task is to find a set of at most k facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem: 
- FPT Approximation Scheme: for any epsilon>0, in time 2^{O(k epsilon^{-3} log (k epsilon^{-1}))}* n^O(1) we can compute a solution that has connection cost at most (1+epsilon) times the optimum, with high probability. 
- Efficient Bicriteria Approximation Scheme: for any epsilon>0, in time 2^{O(epsilon^{-5} log (epsilon^{-1}))}* n^O(1) we can compute a set of at most (1+epsilon)k facilities whose opening yields connection cost at most (1+epsilon) times the optimum connection cost for opening at most k facilities, with high probability. 
As a direct corollary of the second result we obtain an EPTAS for Uniform Facility Location on planar graphs, with same running time.
Our main technical tool is a new construction of a "coreset for facilities" for k-Median in planar graphs: we show that in polynomial time one can compute a subset of facilities F_0 subseteq F of size k * (log n/epsilon)^O(epsilon^{-3}) with a guarantee that there is a (1+epsilon)-approximate solution contained in F_0.

Subject Classification

ACM Subject Classification
  • Theory of computation → Facility location and clustering
  • Theory of computation → Fixed parameter tractability
Keywords
  • k-Median
  • Facility Location
  • Planar Graphs
  • Approximation Scheme

Metrics

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

Related Versions

References

  1. 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
  2. Vladimir Braverman, Dan Feldman, and Harry Lang. New Frameworks for Offline and Streaming Coreset Constructions. CoRR, abs/1612.00889, 2016. URL: http://arxiv.org/abs/1612.00889.
  3. Jarosław 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
  4. Ke Chen. On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. SIAM J. Comput., 39(3):923-947, 2009. Google Scholar
  5. Vincent Cohen-Addad. A Fast Approximation Scheme for Low-dimensional k-means. In SODA 2018, pages 430-440. SIAM, 2018. Google Scholar
  6. Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics. CoRR, abs/1812.08664, 2018. URL: http://arxiv.org/abs/1812.08664.
  7. Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. ICALP'19, 2019. Google Scholar
  8. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. In FOCS 2016, pages 353-364. IEEE Computer Society, 2016. Google Scholar
  9. Vincent Cohen-Addad, Marcin Pilipczuk, and Michał Pilipczuk. A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. In FOCS 2019, 2019. Google Scholar
  10. Vincent Cohen-Addad, Marcin Pilipczuk, and Michal Pilipczuk. Efficient approximation schemes for uniform-cost clustering problems in planar graphs. CoRR, abs/1905.00656, 2019. URL: http://arxiv.org/abs/1905.00656.
  11. Dan Feldman and Michael Langberg. A Unified Framework for Approximating and Clustering Data. CoRR, abs/1106.1379, 2011. Conference version presented at STOC 2011. URL: http://arxiv.org/abs/1106.1379.
  12. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, and Yuval Rabani. Approximation schemes for clustering problems. In STOC 2003, pages 50-58, 2003. Google Scholar
  13. Sudipto Guha and Samir Khuller. Greedy Strikes Back: Improved Facility Location Algorithms. J. Algorithms, 31(1):228-248, 1999. Google Scholar
  14. Sariel Har-Peled. Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons. In SoCG 2014. ACM, 2014. Google Scholar
  15. Dorit S. Hochbaum. Heuristics for the fixed cost median problem. Math. Program., 22(1):148-162, 1982. Google Scholar
  16. K. Jain and 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, 2001. Google Scholar
  17. Amit Kumar, Yogish Sabharwal, and Sandeep Sen. Linear-time approximation schemes for clustering problems in any dimensions. J. ACM, 57(2), 2010. Google Scholar
  18. Shi Li. A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf. Comput., 222:45-58, 2013. Google Scholar
  19. Dániel Marx and Michał Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 865-877. Springer, 2015. See https://arxiv.org/abs/1504.05476 for the full version.
  20. Jiří Matoušek. On Approximate Geometric k-Clustering. Discrete & Computational Geometry, 24(1):61-84, 2000. Google Scholar
  21. Michał Pilipczuk, Erik Jan van Leeuwen, and Andreas Wiese. Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs. In ESA 2018, volume 112 of LIPIcs, pages 65:1-65:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  22. David B Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In STOC 1997, pages 265-274. ACM, 1997. 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 About DROPS Imprint Privacy Contact