New Approaches to the Asymmetric Traveling Salesman and Related Problems

Nima AhmadiPourAnari

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2016-2

January 4, 2016

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-2.pdf

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)<sup>O(1)</sup> which entails a polynomial time log log(n)<sup>O(1)</sup>-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a log log(n)<sup>O(1)</sup> 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)<sup>O(1)</sup>/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)<sup>ε</sup>-approximated in polynomial time for any ε > 0 and that it can be log log(n)<sup>O(1)</sup>-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.

Advisors: Satish Rao

BibTeX citation:

@phdthesis{AhmadiPourAnari:EECS-2016-2,
    Author= {AhmadiPourAnari, Nima},
    Title= {New Approaches to the Asymmetric Traveling Salesman and Related Problems},
    School= {EECS Department, University of California, Berkeley},
    Year= {2016},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-2.html},
    Number= {UCB/EECS-2016-2},
    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 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)<sup>O(1)</sup> which entails a polynomial time log log(n)<sup>O(1)</sup>-estimation algorithm; that is we provide a polynomial time algorithm that finds the cost of the best possible solution within a log log(n)<sup>O(1)</sup> 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)<sup>O(1)</sup>/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)<sup>ε</sup>-approximated in polynomial time for any ε > 0 and that it can be log log(n)<sup>O(1)</sup>-approximated in quasi-polynomial time, assuming access to an oracle which solves our extension of Kadison-Singer.},
}

EndNote citation:

%0 Thesis
%A AhmadiPourAnari, Nima 
%T New Approaches to the Asymmetric Traveling Salesman and Related Problems
%I EECS Department, University of California, Berkeley
%D 2016
%8 January 4
%@ UCB/EECS-2016-2
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-2.html
%F AhmadiPourAnari:EECS-2016-2