Publication Details
Title: When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
Author: A. Frieze, R. M. Karp, and B. Reed
Group: ICSI Technical Reports
Date: November 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-074.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-074
Bibliographic Reference:
A. Frieze, R. M. Karp, and B. Reed. When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?. ICSI Technical Report TR-92-074, November 1992
Author: A. Frieze, R. M. Karp, and B. Reed
Group: ICSI Technical Reports
Date: November 1992
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1992/tr-92-074.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-92-074
Bibliographic Reference:
A. Frieze, R. M. Karp, and B. Reed. When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?. ICSI Technical Report TR-92-074, November 1992