Improved Tours and Paths for the Travelling Salesman
Abstract: 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 sub-tour 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 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. :
About the speaker: Anke van Zuylen is an associate professor of Mathematics at the College of William & Mary. Her research interests are in the design and analysis of algorithms for combinatorial optimization problems arising in areas such as information science, network design, scheduling and logistics, and computational biology. She received a PhD in Operations Research from Cornell University supervised by David P. Williamson in 2008. Before joining Mathematics Department at William & Mary in 2012, she held postdoctoral positions at the Institute for Theoretical Computer Science at Tsinghua University in Beijing, China and at the Max Plank Institute for Informatics in Saarbrucken, Germany as the recipient of the Lise Meitner Award Fellowship for Excellent Women in Computer Science.
For more information, please visit http://www.ankevanzuylen.com/
