 Main
New Approaches to the Asymmetric Traveling Salesman and Related Problems
 Ahmadipouranari, Nima
 Advisor(s): Rao, Satish B
Abstract
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 decadesold $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 HeldKarp 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$edgeconnected 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 KadisonSinger 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 KadisonSinger 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 quasipolynomial time, assuming access to an oracle which solves our extension of KadisonSinger.
Main Content
Enter the password to open this PDF file:













