一种用于欧几里得旅行商问题的Gap-ETH-Tight近似算法

《Journal of the ACM》：A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

最短旅行商问题的近似算法在d维空间中时间复杂度得到优化，提出稀疏性敏感修补新方法，将运行时间从(1/ε)^O(1/ε^{d-1})n log n提升至2^{O(1/ε^{d-1})}n log n，并证明该改进与Gap-ETH假设相容。该技术扩展至Steiner树等问题，同时给出匹配的下界证明。

　　

摘要

我们重新审视了在\(d\)维欧几里得空间中找到\(n\)个点的最短路径这一经典问题，其中\(d \ge 2\)是一个固定的常数。在合理的假设下，我们确定了算法运行时间对\(\varepsilon\)的最优依赖性，该算法能够计算出一个\((1+\varepsilon)\)近似的最短路径。具体来说，我们提出了一种运行时间为\(2^{\mathcal {O}(1/\varepsilon ^{d-1})} n\log n\)的算法。这改进了Rao和Smith（STOC 1998年）提出的算法中之前最小的对\(\varepsilon\)的依赖性，即\((1/\varepsilon)^{\mathcal {O}(1/\varepsilon ^{d-1})}n \log n\)。我们还证明了，如果存在一个运行时间为\(2^{o(1/\varepsilon ^{d-1})}\mathrm{poly}(n)\)的算法，那么它将违反间隙指数时间假设（Gap-ETH）。

我们的新算法建立在Arora（J. ACM 1998年）最初提出的基于四叉树的方法基础上，但增加了一个我们称之为“稀疏敏感修补”（sparsity-sensitive patching）的新思路。从高层次来看，这种方法允许我们根据路径在局部区域的稀疏程度来调整路径简化的粒度。我们通过证明该技术也适用于其他问题（例如斯坦纳树和直线斯坦纳树）来展示其通用性，并为直线斯坦纳树提供了一个与间隙指数时间假设相对应的下界。