Document Open Access Logo

A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP

Author Sándor Kisfaludi-Bak

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.55.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Sándor Kisfaludi-Bak
  • Max Planck Institute for Informatics, Saarbrücken, Germany

Cite As Get BibTex

Sándor Kisfaludi-Bak. A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SoCG.2020.55

Abstract

We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature -1. Let α denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an n^{O(log² n)max(1,1/α)} algorithm for Hyperbolic TSP. This is quasi-polynomial time if α is at least some absolute constant, and it grows to n^O(√n) as α decreases to log² n/√n. (For even smaller values of α, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of n^O(√n).)

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • Computational geometry
  • Hyperbolic geometry
  • Traveling salesman

Metrics

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

Related Versions

References

  1. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM, 45(5):753-782, 1998. URL: https://doi.org/10.1145/290179.290180.
  2. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563-1581, 2016. URL: https://doi.org/10.1137/130913328.
  3. Richard Bellman. Dynamic programming treatment of the travelling salesman problem. Journal of the ACM, 9(1):61-63, 1962. URL: https://doi.org/10.1145/321105.321111.
  4. Riccardo Benedetti and Carlo Petronio. Lectures on hyperbolic geometry. Springer Science & Business Media, 2012. Google Scholar
  5. James W Cannon, William J Floyd, Richard Kenyon, Walter R Parry, et al. Hyperbolic geometry. Flavors of geometry, 31:59-115, 1997. Google Scholar
  6. Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegie Mellon University, 1976. Google Scholar
  7. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay. An ETH-tight exact algorithm for Euclidean TSP. In Proceedings of FOCS 2018, pages 450-461. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00050.
  8. Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. A framework for ETH-tight algorithms and lower bounds in geometric intersection graphs. In Proceedings of STOC 2018, pages 574-586, 2018. URL: https://doi.org/10.1145/3188745.3188854.
  9. Vladimir G. Deineko, Bettina Klinz, and Gerhard J. Woeginger. Exact algorithms for the Hamiltonian cycle problem in planar graphs. Operations Research Letters, 34(3):269-274, 2006. URL: https://doi.org/10.1016/j.orl.2005.04.013.
  10. Marvin J Greenberg. Euclidean and non-Euclidean geometries: Development and history. Macmillan, 1993. Google Scholar
  11. Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems. In Proceedings of the 1961 16th ACM National Meeting, ACM '61, pages 71.201-71.204, New York, NY, USA, 1961. ACM. Google Scholar
  12. 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. URL: https://doi.org/10.1007/BF01228511.
  13. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
  14. Shreesh Jadhav and Asish Mukhopadhyay. Computing a centerpoint of a finite planar set of points in linear time. Discrete & Computational Geometry, 12:291-312, 1994. URL: https://doi.org/10.1007/BF02574382.
  15. Viggo Kann. On the approximability of NP-complete optimization problems. PhD thesis, Royal Institute of Technology Stockholm, 1992. Google Scholar
  16. Richard M. Karp. Reducibility among combinatorial problems. In 50 Years of Integer Programming, pages 219-241. Springer, 2010. Google Scholar
  17. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. J. Comput. Syst. Sci., 81(8):1665-1677, 2015. URL: https://doi.org/10.1016/j.jcss.2015.06.003.
  18. Sándor Kisfaludi-Bak. Hyperbolic intersection graphs and (quasi)-polynomial time. In Proceedings of SODA 2020, pages 1621-1638. SIAM, 2020. URL: https://doi.org/10.1137/1.9781611975994.100.
  19. Sándor Kisfaludi-Bak. A quasi-polynomial algorithm for well-spaced hyperbolic TSP. CoRR, abs/2002.05414, 2020. URL: http://arxiv.org/abs/2002.05414.
  20. Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In Proceedings of FOCS 2006, pages 119-132, 2006. URL: https://doi.org/10.1109/FOCS.2006.9.
  21. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4):1298-1309, 1999. URL: https://doi.org/10.1137/S0097539796309764.
  22. Arlan Ramsay, Robert Davis Richtmyer, and Robert D. Richtmyer. Introduction to hyperbolic geometry. Universitext. Springer, New York, 1995. Google Scholar
  23. Satish Rao and Warren D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pages 540-550. ACM, 1998. URL: https://doi.org/10.1145/276698.276868.
  24. Warren D. Smith and Nicholas C. Wormald. Geometric separator theorems & applications. In Proceedings of FOCS 2018, pages 232-243. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743449.
  25. Aleksandr S. Smogorževskij. Lobatschewskische Geometrie. Mathematische Schülerbücherei 96. Teubner, Leipzig, 1. aufl. edition, 1978. Google Scholar
  26. William P. Thurston. Three-Dimensional Geometry and Topology, volume 1. Princeton University Press, 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