An ETH-tight exact algorithm for euclidean TSP

Mark T. de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay

Research output: Contribution to journalArticleAcademic

35 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article number1807.06933v2
Number of pages17
JournalarXiv
Publication statusPublished - 2018

Cite this