N&O seminar: Hans Bodlaender (UU)

An ETH-Tight Algorithm for Euclidean TSP
  • What Networks & Optimization English Seminars
  • When 05-12-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC100)
  • Where L016
  • Contact Name
  • Web Visit external website
  • Add event to calendar iCal

In this paper, the Traveling Salesman Problem is studied, where cities are points in d-dimensional space, and distances are the Euclidean distances. In this paper, the exact computational complexity of this problem is settled, assuming the Exponential Time Hypothesis: for each d >= 2, we give an algorithm that uses time 2^{O(n^{1/d})}. From earlier work, it follows that these bounds are sharp, under the assumption of the ETH.
This is joint work with Mark de Berg, Sándor Kisfaludi-Bak and Sudeshna Kolay.