An ETH-tight exact algorithm for euclidean TSP

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

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 languageEnglish
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
Place of PublicationPiscataway
PublisherIEEE Computer Society
Pages450-461
Number of pages12
ISBN (Electronic)978-1-5386-4230-6
DOIs
Publication statusPublished - 30 Nov 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: 7 Oct 20189 Oct 2018

Conference

Conference59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period7/10/189/10/18

Keywords

  • ETH
  • Euclidean TSP
  • Separator theorem
  • Subexponential algorithms
  • separator theorem

Cite this