The Asymmetric Traveling Salesman Problem

Date

December 14, 2009

Speaker

Shayan Oveis Gharan

Affiliation

Stanford

Overview

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.