The probabilistic relationship between the assignment and asymmetric traveling salesman problems

Abstract

We consider the gap between the cost of an optimal assignment in a complete bipartite graph with random edge weights, and the cost of an optimal traveling salesman tour in a complete directed graph with the same edge weights. Using an improved "patching" heuristic, we show that with high probability the gap is O((ln n) 2/n), and that its expectation is Ω(1/n). One of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation ⊖(ln n/n). A consequence of the small assignment-TSP gap is an e Õ(√n)-time algorithm which, with high probability, exactly solves a random asymmetric traveling salesman instance. In addition to the assignment-TSP gap, we also consider the expected gap between the optimal and second-best assignments; it is at least Ω(1/n 2) and at most O(ln n/n 2). © 2007 Society for Industrial and Applied Mathematics.