Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
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.
Victor Valls, Panagiotis Promponas, et al.
IEEE Communications Magazine
B. Wagle
EJOR
Liat Ein-Dor, Y. Goldschmidt, et al.
IBM J. Res. Dev
Rajeev Gupta, Shourya Roy, et al.
ICAC 2006