
Discrete Mathematics and Optimization Seminar

Nov. 8nd, 2010
Approximating the Asymmetric Traveling Salesman Problem
Michel Goemans
MIT

Abstract: The traveling salesman problem (TSP)  the problem of finding the
shortest tour through a set of cities  is the prototypical
combinatorial optimization problem. It comes in two flavors, the
symmetric (STSP) and asymmetric (ATSP) versions; the latter
corresponds to the setting in which the cost of traveling from A to B
might differ from the cost from B to A. Whether one can efficiently
find solutions in the asymmetric case that are within a constant
factor of optimal has proved to be elusive despite considerable
efforts, while the same question in the symmetric case has been
settled for decades.
In this talk, I will describe a randomized algorithm for ATSP which
delivers a solution within a factor $O(\log n/ \log\log n)$ of the
optimum. This is the first approximation algorithm that breaks the
logarithmic glass ceiling of approximability. The algorithm is
somewhat reminiscent of Christofides' algorithm for the symmetric
case. It first solves the classical HeldKarp linear programming
relaxation of the problem, then generates a spanning tree T while
disregarding the orientations of the arcs, and finally augments it
into a directed Eulerian graph at minimum cost by solving a minimum
cost flow problem. The cost of the final step depends on the {\it
thinness} of the tree T. Negatively correlated distributions give
trees which are sufficiently thin with high probability, and ways to
obtain such distributions for spanning trees will be discussed.
During the talk, our tour will bring us to visit polyhedral arguments,
negative correlation, random spanning trees, maximum entropy
distributions, approximate minimum cuts, Kirchhoff's matrix tree
theorem, and several other concepts. The talk will leave many
questions open.
The main result is joint with Arash Asadpour, Aleksander Madry, Shayan
Oveis Gharan and Amin Saberi.



