Fall 2014

SGT Seminar

Monday, December 15th, 2014, 2:00 pm3:00 pm

Add to Calendar


Shayan Oveis Gharan (University of Washington)


Calvin Lab 116

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.