A gap-ETH-tight approximation scheme for Euclidean TSP

S Kisfaludi-Bak, J Nederlof… - 2021 IEEE 62nd Annual …, 2022 - ieeexplore.ieee.org
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science …, 2022ieeexplore.ieee.org
We revisit the classic task of finding the shortest tour of n, points in d-dimensional Euclidean
space, for any fixed constant d\geqslant2. We determine the optimal dependence on ε in the
running time of an algorithm that computes a (1+ε)- approximate tour, under a plausible
assumption, Specifically, we give an algorithm that runs in 2^O(1/ε^d-1)n\logn time. This
improves the previously smallest dependence on ε in the running time (1/ε)^O(1/ε^d-1)n\logn
of the algorithm by Rao and Smith (STOC 1998). We also show that a 2^o(1/ε^d-1)poly(n) …
We revisit the classic task of finding the shortest tour of , points in d-dimensional Euclidean space, for any fixed constant . We determine the optimal dependence on in the running time of an algorithm that computes a approximate tour, under a plausible assumption, Specifically, we give an algorithm that runs in time. This improves the previously smallest dependence on in the running time of the algorithm by Rao and Smith (STOC 1998). We also show that a algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call sparsity-sensitive patching. On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-Ethlower bound for Rectilinear Steiner Tree.
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果