hide
Free keywords:
Computer Science, Computational Geometry, cs.CG,Computer Science, Computational Complexity, cs.CC,Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We revisit the classic task of finding the shortest tour of $n$ points in
$d$-dimensional Euclidean space, for any fixed constant $d \geq 2$. We
determine the optimal dependence on $\varepsilon$ in the running time of an
algorithm that computes a $(1+\varepsilon)$-approximate tour, under a plausible
assumption. Specifically, we give an algorithm that runs in
$2^{\mathcal{O}(1/\varepsilon^{d-1})} n\log n$ time. This improves the
previously smallest dependence on $\varepsilon$ in the running time
$(1/\varepsilon)^{\mathcal{O}(1/\varepsilon^{d-1})}n \log n$ of the algorithm
by Rao and Smith (STOC 1998). We also show that a
$2^{o(1/\varepsilon^{d-1})}\text{poly}(n)$ algorithm would violate the
Gap-Exponential Time Hypothesis (Gap-ETH).
Our new algorithm builds upon the celebrated quadtree-based methods initially
proposed by Arora (J. ACM 1998), but it adds a simple new idea that we call
\emph{sparsity-sensitive patching}. On a high level this lets the granularity
with which we simplify the tour depend on how sparse it is locally. Our
approach is (arguably) simpler than the one by Rao and Smith since it can work
without geometric spanners. We demonstrate the technique extends easily to
other problems, by showing as an example that it also yields a Gap-ETH-tight
approximation scheme for Rectilinear Steiner Tree.
