Approximating ATSP by Relaxing Connectivity

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 significantly 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.

Authors

• Ola Svensson

Keywords

• Approximation methods
• Approximation algorithms
• Measurement
• Traveling salesman problems
• Algorithm design and analysis
• Cities and towns
• Polynomials
• Asymmetric Travelling Salesman Problem
• Leisure
• Estimation Algorithm
• Shortest Path
• Algorithm For Problem
• Local Connectivity
• Constant Approximation
• Traveling Salesman Problem
• Performance Guarantees
• General Metrics
• Easy Problem
• Linear Programming Relaxation
• Light Cycle
• Efficient Algorithm
• Proof Of Theorem
• Linear Programming
• Edge Weights
• Directed Graph
• Triangle Inequality
• Polynomial-time Algorithm
• Merging Procedure
• Unweighted Graph
• Proof Of The Lemma
• Update Phase
• Knapsack Problem
• Subset Of Edges
• Notorious Problem
• Algorithm Execution
• Lexicographic
• Multiset
• asymmetric traveling salesman problem
• combinatorial optimization