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 x n matrix ll I 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) --> infinity with rt then we prove that ATSP(M) = AP(M) with probability l-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(n) --> 0 then Pr(ATSP(M)= AP(M)) --> 0.