ON RANDOM SYMMETRIC TRAVELLING SALESMAN PROBLEMS

ALAN FRIEZE

Carnegie Mellon University

April 29, 4:15pm
2-105

ABSTRACT 


Let the edges of the complete graph Kn be assigned independent uniform
[0,1] random edge weights. Let TSP and 2FAC be the weights of the minimum
length traveling salesman tour and minimum weight 2-factor respectively.
We show that with high probability |TSP-2FAC|=o(1). The proof is via by
the analysis of a polynomial time algorithm that finds a tour only a
little longer than 2FAC.





Return to Applied Math Colloquium home page