When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
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\times 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_n that any particular entry is zero. If np_n\rightarrow \infty with n then we prove that ATSP(M)=AP(M) with probability 1-o(1).
