×

When is the assignment bound tight for the asymmetric traveling-salesman problem? (English) Zbl 0833.90096

It is well-known that the assignment problem serves as an upper bound to the asymmetric traveling salesman problem. In this paper, it is shown that if the entries of the cost matrix are drawn independently at random from a common distribution over nonnegative reals then the optimal values for both problems coincide with probability tending to 1 as \(n\to \infty\) if the expected number of zeros in each row diverges to infinity. This extends earlier results by several authors where the uniform distribution over the interval [0, 1]was instead considered.

MSC:

90C27 Combinatorial optimization
05C80 Random graphs (graph-theoretic aspects)
90C35 Programming involving graphs or networks
90B80 Discrete location and assignment
Full Text: DOI