TCS+ Online 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 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). We prove this by showing that any k-edge-connected unweighted graph with k≥7log(n) has a polylog(k)/k-thin spanning tree.

Our main new ingredient is a procedure, albeit an exponentially sized convex program, that "transforms" graphs that do not admit any spectrally thin trees into those that provably have spectrally thin trees. More precisely, given a k-edge-connected graph G=(V,E) where k≥7log(n), we show that there is a matrix D that "preserves" the structure of all cuts of G such that for a set F⊆E that induces an Ω(k)-connected graph, the effective resistance of every edge in F w.r.t. D is at most O(polylog(k)/k). Then, we use a recent extension of the seminal work of Marcus, Spielman and Srivastava [MSS13] by the authors [AO14b] to prove the existence of an O(polylog(k)/k)-spectrally thin tree with respect to D. Such a tree is O(polylog(k)/k)-combinatorially thin with respect to G as D preserves the structure of cuts of G.