An ETH-tight exact algorithm for euclidean TSP

We study exact algorithms for {\sc Euclidean TSP} in Rd. In the early 1990s algorithms with nO(n√) running time were presented for the planar case, and some years later an algorithm with nO(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 {\sc Euclidean TSP}, except for a lower bound stating that the problem admits no 2O(n1−1/d−ϵ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of {\sc Euclidean TSP} by giving a 2O(n1−1/d) algorithm and by showing that a 2o(n1−1/d) algorithm does not exist unless ETH fails.