×

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
Full Text: DOI