Focus on Faculty Talk: Anastasios Sidiropoulos
New Algorithms and Hardness Results for Geometric Instances of TSP
Given a list of cities and the distances between any pair of them the Traveling Salesperson Problem (TSP) asks to find the shortest possible tour that visits all cities. This is one of the most well-studied problems in algorithm design and it is often used as a benchmark for optimization techniques.
An important special case of TSP consists of cities in a geometric space such as a surface or a low-dimensional Euclidean space. We present a new approximation algorithm for the case of surfaces which yields an exponential improvement over the previously best-known result. For the case of Euclidean space we prove that the running time of the currently best-known algorithms are nearly optimal.