论文标题
Euclidean TSP的Gap-Eth紧密近似方案
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
论文作者
论文摘要
对于任何固定常数$ d \ geq 2 $，我们重新审视了在$ d $ d $二维的欧几里得空间中找到最短的$ n $点的经典任务。我们确定了根据合理的假设，在计算$（1+ \ varepsilon）$近似旅行的算法的运行时间内确定了对$ \ varepsilon $的最佳依赖性。具体来说，我们提供了一种算法，该算法以$ 2^{\ Mathcal {o}（1/\ varepsilon^{d-1}）} n \ log n $ time运行。这改善了以前对$ \ varepsilon $在运行时间$（1/\ varepsilon）^{\ Mathcal {o}（1/\ Varepsilon^{d-1}} n \ log log n $的运行时间$（1/\ VAREPSILON）中的依赖性。我们还表明，$ 2^{o（1/\ varepsilon^{d-1}）} \ text {poly}（n）$算法将违反差距指数时间假设（gap-eth）。 我们的新算法建立在Arora最初提出的基于Quadtree的著名方法上（J. ACM 1998），但它添加了一个新想法，我们称为\ emph {sparsity敏感的补丁}。在很高的水平上，这使我们简化了游览的粒度取决于当地的稀疏程度。我们证明了我们的技术扩展到其他问题，通过证明施泰纳树和直线施坦纳树的运行时间相同。我们使用与直线施泰纳树的匹配的GAP-ETH下限相匹配的结果。
We revisit the classic task of finding the shortest tour of $n$ points in $d$-dimensional Euclidean space, for any fixed constant $d \geq 2$. We determine the optimal dependence on $\varepsilon$ in the running time of an algorithm that computes a $(1+\varepsilon)$-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in $2^{\mathcal{O}(1/\varepsilon^{d-1})} n\log n$ time. This improves the previously smallest dependence on $\varepsilon$ in the running time $(1/\varepsilon)^{\mathcal{O}(1/\varepsilon^{d-1})}n \log n$ of the algorithm by Rao and Smith~(STOC 1998). We also show that a $2^{o(1/\varepsilon^{d-1})}\text{poly}(n)$ 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 \emph{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-ETH lower bound for Rectilinear Steiner Tree.
