On Random Symmetric Travelling Salesman Problems

Let the edges of the complete graph K_n be assigned independent uniform [0, 1] random edge weights. Let Z_TSP and Z_2FAC be the weights of the minimum length travelling salesman tour and minimum weight 2-factor, respectively. We show that whp |Z_TSP − Z_2FAC| = o(1). The proof is obtained by the analysis of a polynomial time algorithm that finds a tour only a little longer than Z_2FAC.