SGT Seminar

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

We show that the integrality gap of the natural LP relaxation of the Asymmetric Traveling Salesman Problem is at most 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.