×

The probabilistic relationship between the assignment and asymmetric traveling salesman problems. (English) Zbl 1161.90468

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)\).

MSC:

90C27 Combinatorial optimization
68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
PDFBibTeX XMLCite
Full Text: DOI