UC Berkeley

The Asymmetric Traveling Salesman Problem and its variants are optimization problems that are widely studied from the viewpoint of approximation algorithms as well as hardness of approximation. The natural LP relaxation for ATSP has been conjectured to have an $O(1)$ integrality gap. Recently the best known approximation factor for this problem was improved from the decades-old $O(\log(n))$ to $O(\log(n)/\log\log(n))$ using the connection between ATSP and Goddyn's Thin Tree conjecture.

In this work we show that the integrality gap of the famous Held-Karp LP relaxation for ATSP is bounded by $\log\log(n)^{O(1)}$ which entails a polynomial time $\log\log(n)^{O(1)}$-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a $\log\log(n)^{O(1)}$ factor, but does not provide a solution with that cost. This is one of the very few instances of natural problems studied in approximation algorithms where the state of the art approximation and estimation algorithms do not match.

We prove this by making progress on Goddyn's Thin Tree conjecture; we show that every $k$-edge-connected graph contains a $\log\log(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 rank 1 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)^\epsilon$-approximated in polynomial time for any $\epsilon>0$ and that it can be $\log\log(n)^{O(1)}$-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.