This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Frieze, A. Search for Related Content

On Random Symmetric Travelling Salesman Problems

Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213
alan{at}random.math.cmu.edu

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.

Key Words: travelling salesman; probabilistic analysis
History: Received: November 26, 2002; revision received: September 30, 2003;