A (slightly) Improved Approximation algorithm for Metric TSP
Abstract
In an instance of the (metric) traveling salesperson problem (TSP), we are given a list of n cities and their pairwise symmetric distances satisfying the triangle inequality, and we want to find the shortest tour that visits all cities exactly once and returns back to the starting point. I will talk about an algorithm that provably returns a tour whose cost is at most 50-eps percent more than the optimum where eps > 0 is a small constant independent of n. This slightly improves classical algorithms of Christofides and Serdyukov from the 1970s. The proof exploits a deep connection to the rapidly evolving area of geometry of polynomials. In this area, we encode discrete phenomena, in our case uniform spanning tree distributions, in coefficients of complex multivariate polynomials, and we understand them via the interplay of the coefficients, zeros, and function values of these polynomials. Over the last fifteen years, this perspective has led to several breakthroughs in computer science such as construction of Ramanujan graphs and the Mihail-Vazirani's and Mason's conjectures for matroids. I will discuss how some of the ideas of this field can be used to design and analyze algorithms for TSP. Based on joint work with Anna Karlin and Nathan Klein.
Bio
Shayan Oveis Gharan is an associate professor of the Paul Allen School of Computer Science and Engineering at the University of Washington. He received his Ph.D. from the MS&E department at Stanford University in 2013. Before joining UW, he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley. Shayan's research exploits several tools in Mathematics, such as the theory of real stable and log-concave polynomials, and spectral graph theory, to design and analyze optimization algorithms for discrete objects.
