PIMS-UW Colloquium: Shayan Oveis Gharan

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