Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908877120864256 |
|---|---|
| author | Kisfaludi-Bak, Sándor Odak, Saeed Singh, Satyam van Wordragen, Geert |
| author_facet | Kisfaludi-Bak, Sándor Odak, Saeed Singh, Satyam van Wordragen, Geert |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_09834 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree Kisfaludi-Bak, Sándor Odak, Saeed Singh, Satyam van Wordragen, Geert Computational Geometry 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. |
| title | Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.09834 |