Approximating ATSP by Relaxing Connectivity

  • Ola Svensson | École Polytechnique Fédérale de Lausanne

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments are constructive and give a constant factor approximation algorithm for these metrics. We remark that the considered case is more general than the directed analog of the special case of the symmetric traveling salesman problem for which there were recent improvements on Christofides’ algorithm.

The main idea of our approach is to first consider an easier problem obtained by relaxing the general connectivity requirements into local connectivity conditions. For this relaxed problem, it is quite easy to give an algorithm with a guarantee of 3 on node-weighted shortest path metrics. More surprisingly, we then show that any algorithm (irrespective of the metric) for the relaxed problem can be turned into an algorithm for the asymmetric traveling salesman problem by only losing a small constant factor in the performance guarantee. This leaves open the intriguing task of designing a “good” algorithm for the relaxed problem on general metrics.

Speaker Details

Ola Svensson is an assistant professor in the theory group at EPFL. He is interested in fundamental questions in combinatorial optimization related to the approximability of basic optimization problems. His work on the traveling salesman problem received the best paper award at FOCS’11.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks