EffectiveResistanceReducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Hot Topics: KadisonSinger, Interlacing Polynomials, and Beyond March 09, 2015  March 13, 2015
Location: SLMath: Eisenbud Auditorium
travelling salesman problem
NPhard problems
combinatorial optimization
MarcusSpielmanSrivastava theorem
spectral graph theory
kconnective graph
approximation algorithms
14192
Given a kedgeconnected graph G=(V,E), a spanning tree T is athin w.r.t. G, if for any S⊂V, T(S,V−S)≤a.E(S,V−S). The thin tree conjecture asserts that for a sufficiently large k (independent of size of G) every kedgeconnected graph has a 1/2thin 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 kconnected graph has a polyloglog(n)/kthin 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.
14192
H.264 Video 
14192.mp4

Download 
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.