Mathematical Sciences Research Institute

Home » Workshop » Schedules » Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP

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

Hot Topics: Kadison-Singer, Interlacing Polynomials, and Beyond March 09, 2015 - March 13, 2015

March 13, 2015 (11:00 AM PDT - 12:00 PM PDT)
Speaker(s): Shayan Oveis Gharan (University of Washington)
Location: MSRI: Simons Auditorium


Given a k-edge-connected graph G=(V,E), a spanning tree T is a-thin w.r.t. G, if for any SV, |T(S,VS)|≤a.|E(S,VS)|. The thin tree conjecture asserts that for a sufficiently large k (independent of size of G) every k-edge-connected graph has a 1/2-thin tree. This conjecture can be seen as an L1 analogous of KS_r, for r=k, restricted to graphs. It is intimately related to designing approximation algorithms for Asymmetric Traveling Salesman Problem (ATSP).


In this work, we show that any k-connected graph has a polyloglog(n)/k-thin spanning tree. This implies that the integrality gap of the natural LP relaxation of ATSP 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). This is the first significant improvement over the classical O~(log n) approximation factor for ATSP. Our proof builds on the method of interlacing polynomials of Marcus, Spielman and Srivastava and employs several tools from spectral graph theory and high dimensional geometry.


Based on a joint work with Nima Anari.


Supplements No Notes/Supplements Uploaded
Video/Audio Files


H.264 Video 14192.mp4 345 MB video/mp4 rtsp://videos.msri.org/data/000/023/115/original/14192.mp4 Download
Buy the DVD

If none of the options work for you, you can always buy the DVD of this lecture. The videos are sold at cost for $20USD (shipping included). Please Click Here to send an email to MSRI to purchase the DVD.

See more of our Streaming videos on our main VMath - Streaming Video page.