English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP

MPS-Authors
/persons/resource/persons252857

Kisfaludi-Bak,  Sándor
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons252863

Węgrzycki,  Karol
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (public)

arXiv:2011.03778.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Kisfaludi-Bak, S., Nederlof, J., & Węgrzycki, K. (2020). A Gap-ETH-Tight Approximation Scheme for Euclidean TSP. Retrieved from https://arxiv.org/abs/2011.03778.


Cite as: http://hdl.handle.net/21.11116/0000-0007-7774-1
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.