When is the assignment bound tight for the asymmetric traveling-salesman problem?

Abstract: "We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP(M) and the value of its assignment relaxation AP(M). We assume here that the costs are given by an n x n matrix M whose entries are independently and identically distributed. We focus on the relationship between Pr(ATSP(M) = AP(M)) and the probability p[subscript n] that any particular entry is zero. If np[subscript n] -> [infinity] with n then we prove that ATSP(M) = AP(M) with probability 1-o(1). This is shown to be best possible in the sense that if np(n) -> c, c > 0 and constant, then Pr(ATSP(M) = AP(M)) < 1 - [phi](c) for some positive function [phi]. Finally, if np[subscript n] -> 0 then Pr(ATSP(M) = AP(M)) -> 0."