The Asymmetric Traveling Salesman Problem

Speaker  Shayan Gharan Oveis

Affiliation  Stanford

Host  Jennifer Chayes

Duration  01:09:23

Date recorded  8 December 2009

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.

©2009 Microsoft Corporation. All rights reserved.
> The Asymmetric Traveling Salesman Problem