论文标题
窄带的欧几里得茶匙
Euclidean TSP in Narrow Strips
论文作者
论文摘要
我们调查了euclidean tsp对于点集$ p $的复杂性如何在条带$（ - \ infty，+\ infty）\ times [0，δ] $中取决于条带宽度$δ$。我们获得了两个主要结果。首先，对于这些点具有独特的整数$ x $ - 坐标的情况，我们证明，使用现有算法的最短巡回赛（可以在$ o（n \ log^2 n）$时间计算时，当$δ\ leq 2 \ sqrt {2 \ sqrt {2} $时，总体上是最短的巡回演出，这是最可能的。其次，我们提出了一种相对于$Δ$可固定参数的算法。我们的算法的运行时间$ 2^{o（\sqrtδ）} n + o（δ^2 n^2）$（Δ^2 n^2）$用于稀疏点集，其中每个$ 1 \timesδ$矩形在带中包含$ o（1）$。对于随机点集，其中从矩形$ [0，n] \ times [0，δ] $从随机选择点均匀地选择了点，它的预期运行时间为$ 2^{o（\sqrtδ）} n $。这些结果概括为宽度$δ$的高质量内的点集$ p $。在这种情况下，因子$ 2^{o（\sqrtδ）} $变为$ 2^{o（δ^{1-1/d}）} $。
We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,δ]$ depends on the strip width $δ$. We obtain two main results. First, for the case where the points have distinct integer $x$-coordinates, we prove that a shortest bitonic tour (which can be computed in $O(n\log^2 n)$ time using an existing algorithm) is guaranteed to be a shortest tour overall when $δ\leq 2\sqrt{2}$, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to $δ$. Our algorithm has running time $2^{O(\sqrtδ)} n + O(δ^2 n^2)$ for sparse point sets, where each $1\timesδ$ rectangle inside the strip contains $O(1)$ points. For random point sets, where the points are chosen uniformly at random from the rectangle $[0,n]\times [0,δ]$, it has an expected running time of $2^{O(\sqrtδ)} n$. These results generalise to point sets $P$ inside a hypercylinder of width $δ$. In this case, the factors $2^{O(\sqrtδ)}$ become $2^{O(δ^{1-1/d})}$.
