{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiap2m35awqawjc6vazxeabllttqtm7cgt7ab3jcity27buhtina6i",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgqzq6r6wap2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.09834v1",
  "publishedAt": "2026-03-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Sándor Kisfaludi-Bak",
    "Saeed Odak",
    "Satyam Singh",
    "Geert van Wordragen"
  ],
  "textContent": "**Authors:** Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh, Geert van Wordragen\n\nWe 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"
}