Abstract
In this work we show that the integrality gap of the famous Held-Karp LP relaxation for ATSP is bounded by loglog(n)O(1) which entails a polynomial time loglog(n)O(1)-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a loglog(n)O(1) factor, but does not provide a solution with that cost.
We prove this by making progress on Goddyn's Thin Tree conjecture; we show that every k-edge-connected graph contains a loglog(n)O(1)/k-thin tree. To tackle the Thin Tree conjecture, we build upon the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava. We answer the following question by providing sufficient conditions: Given a set of rank 1 quadratic forms, can we select a subset of them from a given collection of subsets, whose total sum is bounded by a fraction of the sum of all quadratic forms?
We prove this by making progress on Goddyn's Thin Tree conjecture; we show that every k-edge-connected graph contains a loglog(n)O(1)/k-thin tree. To tackle the Thin Tree conjecture, we build upon the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava. We answer the following question by providing sufficient conditions: Given a set of rank 1 quadratic forms, can we select a subset of them from a given collection of subsets, whose total sum is bounded by a fraction of the sum of all quadratic forms?
Finally we address the problem of designing polynomial time approximation algorithms, algorithms that also output a solution, matching the guarantee of the estimation algorithm. We prove that this entirely relies on finding a polynomial time algorithm for our extension of the Kadison-Singer problem. Namely we prove that ATSP can be log(n)c-approximated in polynomial time for any c>0 and that it can be loglog(n)O(1)-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.