When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?

TitleWhen is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
Publication TypeTechnical Report
Year of Publication1992
AuthorsFrieze, A., Karp R. M., & Reed B.
Other Numbers779
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.

URLhttp://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