Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Nima Anari, Shayan Oveis Gharan · 2015
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), where polyloglog(n) is a bounded degree polynomial of loglog(n). We prove this by showing that any k-edge-connected unweighted graph has a polyloglog(n)/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 ≥ 7 log(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)-edge-connected graph, the effective resistance of every edge in F w.r.t. D is at most polylog(k)/k. Then, we use our extension of the seminal work of Marcus, Spielman, and Srivastava [1], fully explained in [2], to prove the existence of a polylog(k)/k-spectrally thin tree with respect to D. Such a tree is polylog(k)/k-combinatorially thin with respect to G as D preserves the structure of cuts of G.