@online{Alkema_arXiv2003.09948,
TITLE = {Euclidean {TSP} in Narrow Strips},
AUTHOR = {Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S{\'a}ndor},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2003.09948},
EPRINT = {2003.09948},
EPRINTTYPE = {arXiv},
YEAR = {2020},
MARGINALMARK = {$\bullet$},
ABSTRACT = {We investigate how the complexity of Euclidean TSP for point sets $P$ inside the strip $(-\infty,+\infty)\times [0,\delta]$ depends on the strip width $\delta$. 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 $\delta\leq 2\sqrt{2}$, a bound which is best possible. Second, we present an algorithm that is fixed-parameter tractable with respect to $\delta$. More precisely, our algorithm has running time $2^{O(\sqrt{\delta})} n^2$ for sparse point sets, where each $1\times\delta$ 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,\delta]$, it has an expected running time of $2^{O(\sqrt{\delta})} n^2 + O(n^3)$.},
}