Document Open Access Logo

The Parameterized Hardness of the k-Center Problem in Transportation Networks

Authors Andreas Emil Feldmann, Dániel Marx

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.19.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Andreas Emil Feldmann
  • Department of Applied Mathematics, Charles University, Prague, Czechia
Dániel Marx
  • Institute for Computer Science and Control, Hungarian Academy of Sciences (MTA SZTAKI), Budapest, Hungary

Funding

  • Feldmann, Andreas Emil: Supported by project CE-ITI (GAČR no. P202/12/G061) of the Czech Science Foundation.
  • Marx, Dániel: Supported by ERC Consolidator Grant SYSTEMATICGRAPH (No. 725978)

Cite As Get BibTex

Andreas Emil Feldmann and Dániel Marx. The Parameterized Hardness of the k-Center Problem in Transportation Networks. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.19

Abstract

In this paper we study the hardness of the k-Center problem on inputs that model transportation networks. For the problem, an edge-weighted graph G=(V,E) and an integer k are given and a center set C subseteq V needs to be chosen such that |C|<= k. The aim is to minimize the maximum distance of any vertex in the graph to the closest center. This problem arises in many applications of logistics, and thus it is natural to consider inputs that model transportation networks. Such inputs are often assumed to be planar graphs, low doubling metrics, or bounded highway dimension graphs. For each of these models, parameterized approximation algorithms have been shown to exist. We complement these results by proving that the k-Center problem is W[1]-hard on planar graphs of constant doubling dimension, where the parameter is the combination of the number of centers k, the highway dimension h, and even the treewidth t. Moreover, under the Exponential Time Hypothesis there is no f(k,t,h)* n^{o(t+sqrt{k+h})} time algorithm for any computable function f. Thus it is unlikely that the optimum solution to k-Center can be found efficiently, even when assuming that the input graph abides to all of the above models for transportation networks at once!
Additionally we give a simple parameterized (1+{epsilon})-approximation algorithm for inputs of doubling dimension d with runtime (k^k/{epsilon}^{O(kd)})* n^{O(1)}. This generalizes a previous result, which considered inputs in D-dimensional L_q metrics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Facility location and clustering
  • Theory of computation → Problems, reductions and completeness
Keywords
  • k-center
  • parameterized complexity
  • planar graphs
  • doubling dimension
  • highway dimension
  • treewidth

Metrics

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

Related Versions

References

  1. I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension and provably efficient shortest path algorithms. Journal of the ACM, 63(5):41, 2016. Google Scholar
  2. I. Abraham, D. Delling, A. Fiat, A.V. Goldberg, and R.F. Werneck. VC-dimension and shortest path algorithms. In ICALP, pages 690-699, 2011. Google Scholar
  3. I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In SODA, pages 782-793, 2010. Google Scholar
  4. P. K. Agarwal and C. M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002. Google Scholar
  5. H. Bast, S. Funke, and D. Matijevic. Ultrafast shortest-path queries via transit nodes. 9th DIMACS Implementation Challenge, 74:175-192, 2009. Google Scholar
  6. H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In transit to constant time shortest-path queries in road networks. In ALENEX, pages 46-59, 2007. Google Scholar
  7. A. Becker, P. N. Klein, and D. Saulpic. Polynomial-time approximation schemes for k-center and bounded-capacity vehicle routing in metrics with bounded highway dimension. ArXiv e-prints, arXiv:1707.08270 [cs.DS], 2017. Google Scholar
  8. M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  9. E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos. Fixed-parameter algorithms for (k,r)-center in planar graphs and map graphs. Transactions on Algorithms, 1(1):33-47, 2005. Google Scholar
  10. Irit Dinur and David Steurer. Analytical approach to parallel repetition. In STOC. ACM Press, 2014. Google Scholar
  11. R. G. Downey and M. R. Fellows. Fundamentals of parameterized complexity. Springer, 2013. Google Scholar
  12. David Eisenstat, Philip N Klein, and Claire Mathieu. Approximating k-center in planar graphs. In SODA, pages 617-627, 2014. Google Scholar
  13. T. Feder and D. Greene. Optimal algorithms for approximate clustering. In STOC, pages 434-444, 1988. Google Scholar
  14. A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post. A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. In ICALP, pages 469-480, 2015. Google Scholar
  15. A. E. Feldmann, W. S. Fung, J. Könemann, and I. Post. A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. ArXiv preprint arXiv:1502.04588, 2015. Google Scholar
  16. Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low highway dimension graphs. In ICALP, pages 588-600. Springer Berlin Heidelberg, 2015. Google Scholar
  17. A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS, pages 534-543, 2003. Google Scholar
  18. D. S. Hochbaum and D. B. Shmoys. A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3):533-550, 1986. Google Scholar
  19. Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos. Structural parameters, tight bounds, and approximation for (k, r)-center. In ISAAC, pages 50:1-50:13, 2017. Google Scholar
  20. P. Klein. Personal communication, 2017. Google Scholar
  21. Daniel Lokshtanov, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. Lossy kernelization. In STOC, pages 224-237. ACM Press, 2017. Google Scholar
  22. D. Marx. Parameterized complexity and approximation algorithms. The Computer Journal, 51(1):60-78, 2008. Google Scholar
  23. Dániel Marx. Efficient approximation schemes for geometric problems? In European Symposium on Algorithms, pages 448-459. Springer, 2005. Google Scholar
  24. Dániel Marx and Michał Pilipczuk. Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. In ESA, pages 865-877. Springer, 2015. Google Scholar
  25. J. Plesník. On the computational complexity of centers locating in a graph. Aplikace matematiky, 25(6):445-452, 1980. Google Scholar
  26. Paul D Seymour and Robin Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B, 58(1):22-33, 1993. Google Scholar
  27. Karthik Srikanta, Bundit Laekhanukit, and Pasin Manurangsi. On the parameterized complexity of approximating dominating set. arXiv preprint, abs/1711.11029, 2017. Google Scholar
  28. V. V. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., 2001. Google Scholar
  29. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. 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