Faster Approximation Scheme for Euclidean $k$-TSP

Abstract

In the Euclidean $k$-traveling salesman problem ($k$-TSP), we are given $n$ points in the $d$-dimensional Euclidean space, for some fixed constant $d\ge 2$, and a positive integer $k$. The goal is to find a shortest tour visiting at least $k$ points. We give an approximation scheme for the Euclidean $k$-TSP in time $n\cdot 2^{O(1/{\epsilon }^{d-1})}\cdot (\log n{)}^{2d^2\cdot 2^d}$. This improves Arora's approximation scheme of running time $n\cdot k\cdot (\log n{)}^{{\left(O\left(\sqrt{d}/\epsilon \right)\right)}^{d-1}}$ [J. ACM 1998]. Our algorithm is Gap-ETH tight and can be derandomized by increasing the running time by a factor $O(n^d)$.