Abstract
We study exact algorithms for E UCLIDEAN 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 2O(n 1-1/d-ϵ ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of E UCLIDEAN TSP by giving a 2 O(n-1/d) algorithm and by showing that a 2 o(n1-1/d ) algorithm does not exist unless ETH fails.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
| Editors | Mikkel Thorup |
| Place of Publication | Piscataway |
| Publisher | IEEE Computer Society |
| Pages | 450-461 |
| Number of pages | 12 |
| ISBN (Electronic) | 978-1-5386-4230-6 |
| DOIs | |
| Publication status | Published - 30 Nov 2018 |
| Event | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: 7 Oct 2018 → 9 Oct 2018 |
Conference
| Conference | 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 |
|---|---|
| Country/Territory | France |
| City | Paris |
| Period | 7/10/18 → 9/10/18 |
Keywords
- ETH
- Euclidean TSP
- Separator theorem
- Subexponential algorithms
- separator theorem