On random symmetric travelling salesman problems. (English) Zbl 1082.05517
Summary: Let the edges of the complete graph \(K_n\) be assigned independent uniform \([0, 1]\) random edge weights. Let \(\text{Z}_{\text{TSP}}\) and \(\text{Z}_{\text{2FAC}}\) be the weights of the minimum length travelling salesman tour and minimum weight 2-factor, respectively. We show that \(\mathbf {whp}\, |\text{Z}_{\text{TSP}} - \text{Z}_{\text{2FAC}}| = o(1)\). The proof is obtained by the analysis of a polynomial time algorithm that finds a tour only a little longer than \(\text{Z}_{\text{2FAC}}\).
MSC:
05C80 | Random graphs (graph-theoretic aspects) |
60C05 | Combinatorial probability |
68W40 | Analysis of algorithms |
90C27 | Combinatorial optimization |
90C59 | Approximation methods and heuristics in mathematical programming |