@techreport{8e0c3322c6d847b3ab15e2ca9d72285e,
title = "An ETH-Tight Exact Algorithm for Euclidean TSP",
abstract = "We study exact algorithms for Euclidean TSP in R d . In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.",
keywords = "Particle separators, Approximation algorithms, Computer science, Complexity theory, Hypercubes, Heuristic algorithms",
author = "Berg, {Mark de} and Bodlaender, {Hans L.} and S{\'a}ndor Kisfaludi-Bak and Sudeshna Kolay",
year = "2018",
doi = "10.48550/arXiv.1807.06933",
language = "English",
series = "CoRR",
publisher = "arXiv",
type = "WorkingPaper",
institution = "arXiv",
}