2026-09-05T11:55:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25871 2026-06-23T12:59:57Z ddc:004 open_access

Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree Kisfaludi-Bak, Sándor Odak, Saeed Singh, Satyam van Wordragen, Geert Hyperbolic traveling salesman problem TSP Hyperbolic Steiner tree problem Approximation scheme Banyan Hyperbolic geometry We give an approximation scheme for the TSP in d-dimensional hyperbolic space that has optimal dependence on ε under Gap-ETH. For any fixed dimension d ≥ 2 and for any ε > 0 our randomized algorithm gives a (1+ε)-approximation in time 2^O(1/ε^{d-1}) n^{1+o(1)}. We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time. Our algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG'25). Moreover, we have a new non-uniform portal placement, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor Kisfaludi-Bak and Saeed Odak and Satyam Singh and Geert van Wordragen 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.64 urn:nbn:de:0030-drops-258710 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.64 eng https://creativecommons.org/licenses/by/4.0/legalcode