An O(log n / loglog n)-approximation algorithm for the Asymmetric Travelling Salesperson problem

In this Thursday's seminar, we will go over the recent SODA 2010 paper which gives an O(log n/loglog n)-approximation algorithm for the Asymmetric Travelling Salesperson (ATSP) problem (paper link), improving over the 1982 result of Frieze et al, which showed an O(log n)-approximation for the problem. In contrast, the symmetric version has seen much better approximations, with the best known being a factor 3/2 algorithm due to Christofedes.

In the ATSP problem, we are given a directed graph with cost on the arcs, and these costs satisfy the triangle inequality, i.e c(u,w) <= c(u,v) + c(v,u). Note that the arc costs need not be symmetric, i.e c(u,v) != c(v,u). The goal is to find a minimum cost cycle which visits all the vertices of the graph.

Since 1928 (until this paper), the best known approximation for this problem has been due to Frieze et al, who give a simple combinatorial algorithm and neat analysis to prove a logarithmic approximability bound. They also bound the integrality gap of the natural LP relaxation for the problem.

In the recent paper, Asadpour et al. consider the same LP and give an improved algorithm (based on rounding the LP) which betters the approximation factor by a factor of loglog n. At a high level, their algorithm does the following:

(i) solve the LP, (ii) ignore arc directions for the time being, and get a fractional solution in the spanning tree polytope, (iii) randomly round this fractional solution to get a random spanning tree which satisfies some thin-ness properties, (iv) re-direct these edges appropriately, (v) augment some extra edges to get back euler tour along the directed arcs.

In the lecture, we will first go over the Christofedes algorithm for STSP and then the Frieze et al. algorithm for ATSP. Then we will present the LP and explain its structural properties. Before presenting the rounding process, we will take a detour into the world of matroids and their associated polytopes and present some recent work of Chekuri et al. on how to round a random point in a matroid polytope into a good vertex solution that satisfies some nice properties. Subsequently, we will use these techniques and give the complete details of their approximation algorithm. We will conclude by explaining the connections with steps (iv) and (v) with the algorithm of Christofedes for the STSP.