Anke van Zuylen (William & Mary)

Improved tours and paths for the traveling salesman: Classical tools and recent advances

The traveling salesman problem (TSP) is one of the most famous and widely studied combinatorial optimization problems. Given a set of cities and pairwise distances, the goal is to find a tour of minimum length that visits every city exactly once. Even if we require the distances to form a metric, the problem remains NP-hard. The classic Christofides’s algorithm finds a tour that has length at most 3/2 times the length of the optimal tour. Despite significant effort, no efficient algorithm has been found in over 40 years that improves on the approximation guarantee of 3/2 achieved by Christofides’s algorithm. A well-known, natural direction for making progress which has also defied improvement is the use of a linear programming (LP) relaxation. The famous “four-thirds” conjecture states that there always exists a tour of length at most 4/3 times the optimal value of the so-called subtour LP relaxation for the TSP. 

Although this conjecture has been open for decades, recent years have seen some exciting progress toward resolving the conjecture, including improved algorithms for approximating the optimal value for several variants such as the graph-TSP (where the input metric is the shortest path metric on an unweighted graph) and the s-t path TSP (where the start and end of the tour are distinct). In this talk, we provide a tour of the recent advances for the metric TSP and in particular the s-t path TSP. We  will highlight some of the new techniques that have been developed, building on classical results in polyhedral combinatorics and combinatorial optimization on trees, matroids, matchings, T-joins, flows and shortest paths.