论文标题
关于旅行推销员问题与线路社区的近似性
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
论文作者
论文摘要
我们研究了欧几里得旅行推销员问题的变体，在这种变体中，我们将获得一组线作为输入，而不是一组分数，目标是找到访问每一行的最短巡回演出。 $ \ mathbb {r}^d $中最著名的上限和下限，带有$ d \ ge 3 $，是$ \ mathrm {np} $ - 硬度和$ o（\ log^3 n）$ - 近似近似算法，这是基于对组式踩踏树的减少的。 我们表明，对于任何$ d \ ge 3 $，$ \ mathbb {r}^d $ in $ \ mathbb {r}^d $中的TSP都是apx-hard。更一般地，这意味着$ k $维平面的TSP不承认任何$ 1 \ le k \ leq d-2 $除非$ \ mathrm {p} = \ mathrm {np {np} $，否则已知$ k = 0 $ k = nyplean（i.e），这给出了这些问题的近似性，这给出了这些问题的近似性，这给出了这些问题的近似性。我们能够以$ d = o（\ log n）$提供更强的不可Xibibibibility因子，这表明与行的TSP不承认$（2-ε）$ - 近似$ d $ dimensions在独特的游戏猜想下。从积极的一面来看，我们利用了施泰纳树问题的限制变体的最新结果，以便给出$ O（\ log^2 n）$ - 近似算法的问题，尽管运行时间为$ n^{o（\ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log \ log n）} $。
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in $\mathbb{R}^d$, with $d\ge 3$, are $\mathrm{NP}$-hardness and an $O(\log^3 n)$-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in $\mathbb{R}^d$ is APX-hard for any $d\ge 3$. More generally, this implies that TSP with $k$-dimensional flats does not admit a PTAS for any $1\le k \leq d-2$ unless $\mathrm{P}=\mathrm{NP}$, which gives a complete classification of the approximability of these problems, as there are known PTASes for $k=0$ (i.e., points) and $k=d-1$ (hyperplanes). We are able to give a stronger inapproximability factor for $d=O(\log n)$ by showing that TSP with lines does not admit a $(2-ε)$-approximation in $d$ dimensions under the unique games conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an $O(\log^2 n)$-approximation algorithm for the problem, albeit with a running time of $n^{O(\log\log n)}$.
