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

94 Downloads (Pure)


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
Publication statusPublished - 2018


Dive into the research topics of 'An ETH-tight exact algorithm for euclidean TSP'. Together they form a unique fingerprint.

Cite this