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

Abstract: 

Given a k-edge-connected graph G=(V,E), a spanning tree T is [\alpha] -thin w.r.t. G, if for any $S\subset V$, $|T(S,V−S)|≤\alpha.|E(S,V−S)|$. 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 is intimately related to designing approximation algorithms for Asymmetric Traveling Salesman Problem (ATSP).

We show that any k-edge-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 [\tilde{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 theory and high dimensional geometry.

Based on a joint work with Nima Anari.