When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
Title | When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? |
Publication Type | Technical Report |
Year of Publication | 1992 |
Authors | Frieze, A., Karp R. M., & Reed B. |
Other Numbers | 779 |
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_n that any particular entry is zero. If np_n ? ? 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 - ?(c) for some positive function ?. Finally, if np_n ? 0 then Pr(ATSP(M) = AP(M)) ? 0. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1992/tr-92-074.pdf |
Bibliographic Notes | ICSI Technical Report TR-92-074 |
Abbreviated Authors | A. Frieze, R. M. Karp, and B. Reed |
ICSI Publication Type | Technical Report |