# An ETH-Tight Exact Algorithm for Euclidean TSP

arXiv: https://arxiv.org/abs/1807.06933 · HTML: https://mlsanity.com/paper/1807.06933/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2018.

## Built on by (most cited first, 1 of 1)

- [Test-Time Augmentation for Traveling Salesperson Problem](https://mlsanity.com/paper/2405.04767/) (2024)

## Abstract (arXiv)

We study exact algorithms for Euclidean TSP in ℝ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(n1-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.