Document Open Access Logo

Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d

Authors Rajesh Chitnis, Nitin Saurabh

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.28.pdf
  • Filesize: 0.83 MB
  • 15 pages

Document Identifiers

Author Details

Rajesh Chitnis
  • School of Computer Science, University of Birmingham, UK
Nitin Saurabh
  • Indian Institute of Technology Hyderabad, Sangareddy, India

Cite As Get BibTex

Rajesh Chitnis and Nitin Saurabh. Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.28

Abstract

In the discrete k-Center problem, we are given a metric space (P,dist) where |P| = n and the goal is to select a set C ⊆ P of k centers which minimizes the maximum distance of a point in P from its nearest center. For any ε > 0, Agarwal and Procopiuc [SODA '98, Algorithmica '02] designed an (1+ε)-approximation algorithm for this problem in d-dimensional Euclidean space which runs in O(dn log k) + (k/ε)^{O (k^{1-1/d})}⋅ n^{O(1)} time. In this paper we show that their algorithm is essentially optimal: if for some d ≥ 2 and some computable function f, there is an f(k)⋅(1/ε)^{o (k^{1-1/d})} ⋅ n^{o (k^{1-1/d})} time algorithm for (1+ε)-approximating the discrete k-Center on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails.
We obtain our lower bound by designing a gap reduction from a d-dimensional constraint satisfaction problem (CSP) to discrete d-dimensional k-Center. This reduction has the property that there is a fixed value ε (depending on the CSP) such that the optimal radius of k-Center instances corresponding to satisfiable and unsatisfiable instances of the CSP is < 1 and ≥ (1+ε) respectively. Our claimed lower bound on the running time for approximating discrete k-Center in d-dimensions then follows from the lower bound due to Marx and Sidiropoulos [SoCG '14] for checking the satisfiability of the aforementioned d-dimensional CSP.
As a byproduct of our reduction, we also obtain that the exact algorithm of Agarwal and Procopiuc [SODA '98, Algorithmica '02] which runs in n^{O (d⋅ k^{1-1/d})} time for discrete k-Center on n points in d-dimensional Euclidean space is asymptotically optimal. Formally, we show that if for some d ≥ 2 and some computable function f, there is an f(k)⋅n^{o (k^{1-1/d})} time exact algorithm for the discrete k-Center problem on n points in d-dimensional Euclidean space then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower bound was only known for d = 2 and was implicit in the work of Marx [IWPEC '06].

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • k-center
  • Euclidean space
  • Exponential Time Hypothesis (ETH)
  • lower bound

Metrics

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

Related Versions

References

  1. Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, and Nicolas Trotignon. Coloring graphs with constraints on connectivity. Journal of Graph Theory, 85(4):814-838, 2017. Google Scholar
  2. Pankaj K. Agarwal and Cecilia Magdalena Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002. Google Scholar
  3. Jochen Alber and Jirí Fiala. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithms, 52(2):134-151, 2004. Google Scholar
  4. Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In ESA 2018, volume 112, pages 8:1-8:15, 2018. Google Scholar
  5. Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Pawel Rzazewski. Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom., 9(2):47-80, 2018. URL: https://doi.org/10.20382/jocg.v9i2a4.
  6. Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, and Günter Rote. Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension. ACM Trans. Algorithms, 7(4):43:1-43:27, 2011. URL: https://doi.org/10.1145/2000807.2000811.
  7. Rajesh Chitnis and Nitin Saurabh. Tight Lower Bounds for Approximate & Exact k-Center in ℝ^d. CoRR, abs/2203.08328, 2022. URL: http://arxiv.org/abs/2203.08328.
  8. Rajesh Hemant Chitnis, Andreas Emil Feldmann, Mohammad Taghi Hajiaghayi, and Dániel Marx. Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions). SIAM J. Comput., 49(2):318-364, 2020. Google Scholar
  9. Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman. The Bane of Low-Dimensionality Clustering. In SODA 2018, pages 441-456, 2018. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay. An ETH-Tight Exact Algorithm for Euclidean TSP. In FOCS 2018, pages 450-461, 2018. URL: https://doi.org/10.1109/FOCS.2018.00050.
  12. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs. SIAM J. Comput., 49(6):1291-1331, 2020. URL: https://doi.org/10.1137/20M1320870.
  13. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs. ACM Trans. Algorithms, 1(1):33-47, 2005. Google Scholar
  14. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM, 52(6):866-893, 2005. Google Scholar
  15. Andreas Emil Feldmann. Fixed-parameter approximations for k-center problems in low highway dimension graphs. Algorithmica, 81(3):1031-1052, 2019. Google Scholar
  16. Andreas Emil Feldmann and Dániel Marx. The parameterized hardness of the k-center problem in transportation networks. Algorithmica, 82(7):1989-2005, 2020. Google Scholar
  17. Fedor V. Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In SoCG 2016, pages 39:1-39:15, 2016. Google Scholar
  18. Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. In FOCS 2016, pages 515-524, 2016. Google Scholar
  19. Eli Fox-Epstein, Philip N. Klein, and Aaron Schild. Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. In SODA 2019, pages 1069-1088, 2019. Google Scholar
  20. Yogesh A. Girdhar and Gregory Dudek. Efficient on-line data summarization using extremum summaries. In ICRA 2012, pages 3490-3496, 2012. Google Scholar
  21. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci., 38:293-306, 1985. Google Scholar
  22. S. Louis Hakimi. Steiner’s problem in graphs and its implications. Networks, 1(2):113-133, 1971. Google Scholar
  23. Christian Hennig, Marina Meila, Fionn Murtagh, and Roberto Rocci. Handbook of cluster analysis. CRC Press, 2015. Google Scholar
  24. Dorit S. Hochbaum and David B. Shmoys. A best possible heuristic for the k-center problem. Math. Oper. Res., 10(2):180-184, 1985. Google Scholar
  25. Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discret. Appl. Math., 1(3):209-215, 1979. Google Scholar
  26. R. Z. Hwang, R. C. Chang, and Richard C. T. Lee. The Searching over Separators Strategy To Solve Some NP-Hard Problems in Subexponential Time. Algorithmica, 9(4):398-423, 1993. Google Scholar
  27. R. Z. Hwang, Richard C. T. Lee, and R. C. Chang. The Slab Dividing Approach To Solve the Euclidean p-Center Problem. Algorithmica, 9(1):1-22, 1993. Google Scholar
  28. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  29. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  30. Daxin Jiang, Chun Tang, and Aidong Zhang. Cluster analysis for gene expression data: a survey. IEEE Transactions on knowledge and data engineering, 16(11):1370-1386, 2004. Google Scholar
  31. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. Discret. Appl. Math., 264:90-117, 2019. Google Scholar
  32. Philip N. Klein and Dániel Marx. Solving Planar k-Terminal Cut in O(n^c √k) Time. In ICALP 2012, pages 569-580, 2012. Google Scholar
  33. Philip N. Klein and Dániel Marx. A subexponential parameterized algorithm for Subset TSP on planar graphs. In SODA 2014, pages 1812-1830, 2014. Google Scholar
  34. Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström. Subexponential Parameterized Odd Cycle Transversal on Planar Graphs. In FSTTCS 2012, pages 424-434, 2012. Google Scholar
  35. Dániel Marx. Efficient Approximation Schemes for Geometric Problems? In ESA 2005, pages 448-459, 2005. URL: https://doi.org/10.1007/11561071_41.
  36. Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Hans L. Bodlaender and Michael A. Langston, editors, IWPEC 2006, pages 154-165, 2006. Google Scholar
  37. Dániel Marx. A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals. In ICALP 2012, pages 677-688, 2012. Google Scholar
  38. Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk. On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs. In FOCS 2018, pages 474-484, 2018. Google Scholar
  39. Dániel Marx and Michal Pilipczuk. Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams. In ESA 2015, pages 865-877, 2015. Google Scholar
  40. Dániel Marx and Anastasios Sidiropoulos. The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems. In SoCG 2014, page 67, 2014. Google Scholar
  41. Marie-Francine Moens, Caroline Uyttendaele, and Jos Dumortier. Abstracting of legal cases: The potential of clustering based on the selection of representative objects. J. Am. Soc. Inf. Sci., 50(2):151-161, 1999. Google Scholar
  42. Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen. Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs. In STACS 2013, pages 353-364, 2013. Google Scholar
  43. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications. In FOCS 1998, pages 232-243, 1998. Google Scholar
  44. Vijay V. Vazirani. Approximation algorithms. Springer, 2001. 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