Frieze, Alan; Sorkin, Gregory B. The probabilistic relationship between the assignment and asymmetric traveling salesman problems. (English) Zbl 1161.90468 SIAM J. Comput. 36, No. 5, 1435-1452 (2007). Summary: 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 \(\Omega(1/n)\). One of the underpinnings of this result is that the largest edge weight in an optimal assignment has expectation \(\Theta(\ln n / n)\). A consequence of the small assignment – TSP gap is an \(e^{\tilde{O}(\sqrt{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 \(\Omega(1/n^2)\) and at most \(O(\ln n/n^2)\). Cited in 4 Documents MSC: 90C27 Combinatorial optimization 68Q25 Analysis of algorithms and problem complexity 68W40 Analysis of algorithms 05C80 Random graphs (graph-theoretic aspects) 60C05 Combinatorial probability Keywords:Assignment problem; asymmetric traveling salesman problem; average-case analysis of algorithms; random assignment problem; matching; alternating path; patching heuristic; cycle cover; permutation digraph; near-permutation digraph PDFBibTeX XMLCite \textit{A. Frieze} and \textit{G. B. Sorkin}, SIAM J. Comput. 36, No. 5, 1435--1452 (2007; Zbl 1161.90468) Full Text: DOI