N&O seminar: Hans Bodlaender (UU)

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.