Speaker Shayan Gharan Oveis
Host Jennifer Chayes
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.