N&O seminar: Hans Bodlaender (UU)
An ETH-Tight Algorithm for Euclidean TSP
- https://www.cwi.nl/research/groups/networks-and-optimization/events/n-o-seminar-hans-bodlaender-uu
- N&O seminar: Hans Bodlaender (UU)
- 2018-12-05T11:00:00+01:00
- 2018-12-05T12:00:00+01:00
- An ETH-Tight Algorithm for Euclidean TSP
- What Networks & Optimization English
- When 05-12-2018 from 11:00 to 12:00 (Europe/Amsterdam / UTC100)
- Where L016
- Contact Name Daniel Dadush
- 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.