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 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 and Mathematics such as simpler proofs of the van-der-Waerden conjecture, and resolutions of the Kadison-Singer and the Mihail-Vazirani conjectures. I will discuss how properties of strongly Rayleigh distributions, a family of probability distributions whose generating polynomial is real stable, can be used to design and analyze algorithms for TSP.
Based on a joint work with Anna Karlin and Nathan Klein.
Zoom Link: https://washington.zoom.us/j/97220430761
Shayan Oveis Gharan is an associate professor in the Paul Allen School of Computer Science and Engineering at University of Washington. He received his PhD from the Management Science and Engineering 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 theory of real stable and log-concave polynomials, and spectral graph theory to design and analyze algorithms for discrete objects.