About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIAM Journal on Computing
Paper
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.