The Asymmetric Traveling Salesman Problem

We consider the asymmetric traveling salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability. Also we give the first constant factor approximation algorithm for metrics that are shortest path distances in a weighted directed graph when the underlying undirected graph has a bounded orientable genus. In this talk I will try to describe the main ideas of these algorithms.

Our approach for ATSP has similarities with Christofides’ algorithm; we first construct a spanning tree with special properties. Then we find a minimum cost Eulerian augmentation of this tree, and finally, shortcut the resulting Eulerian walk.