Effective-Resistance-Reducing Flows, Spectrally Thin Trees and Asymmetric TSP

  • Shayan Oveis-Gharan | University of Washington

We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is at most polyloglog(n). In other words, there is a polynomial time algorithm that approximates the value of the optimum tour within a factor of polyloglog(n). To prove this, we show that any k-edge-connected graph (for k=Omega(log(n))) has a polylog(k)/k thin tree. In this talk I will highlight the main ideas of our proof. This is a joint work with Nima Anari.

Speaker Details

Shayan Oveis Gharan is an assistant professor at CSE department at UW. He received his PhD from the MS&E department at Stanford University. His is mainly interested in the design and analysis of algorithms. In the past, he received several awards for his works on the Traveling Salesman Problem.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks