Paper Info
Title
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP
Abstract
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 log log(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>= 7log(n), we show that there is a matrix D that "preserves" the structure of all cuts of G such that for a subset F of E that induces an O(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 recent extension of the seminal work of Marcus, Spiel man, and Srivastava [MSS13] 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.
Year
DOI
Venue
2015
10.1109/FOCS.2015.11
IEEE Symposium on Foundations of Computer Science
Keywords
Field
DocType
Asymmetric Traveling Salesman Problem,Approximation Algorithms,Thin Tree Conjecture,Kadison-Singer Problem,Effective Resistance
Approximation algorithm,Discrete mathematics,Combinatorics,Polynomial,Degree of a polynomial,Travelling salesman problem,Spanning tree,Linear programming relaxation,Time complexity,Mathematics,Bounded function
Conference
ISSN
Citations 
PageRank 
0272-5428
8
0.53
References 
Authors
23
2
Name
Order
Citations
PageRank
Nima Anari17914.83
Shayan Oveis Gharan232326.63