DMO Seminar

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 Held-Karp 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.