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.
Reviewer: A.Ruciński (Poznań)
MSC:
90C27 | Combinatorial optimization |
05C80 | Random graphs (graph-theoretic aspects) |
90C35 | Programming involving graphs or networks |
90B80 | Discrete location and assignment |