Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
This provides efficient algorithms for geometric optimization in curved spaces, addressing a specific domain with incremental improvements over prior methods.
The paper tackles the Traveling Salesman Problem (TSP) and Steiner tree problem in hyperbolic space by developing an approximation scheme with optimal dependence on ε under Gap-ETH, achieving a (1+ε)-approximation in time 2^{O(1/ε^{d-1})}n^{1+o(1)} for fixed dimensions d≥2.
We give an approximation scheme for the TSP in $d$-dimensional hyperbolic space that has optimal dependence on $\varepsilon$ under Gap-ETH. For any fixed dimension $d\geq 2$ and for any $\varepsilon>0$ our randomized algorithm gives a $(1+\varepsilon)$-approximation in time $2^{O(1/\varepsilon^{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.