On random symmetric travelling salesman problems

• 成果类型: Article
• 署名作者: Frieze, A
• 署名单位: Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0105
• 发表日期: 2004
• 页码: 878-890
• 关键词: Random assignment problem; graphs; algorithms

摘要

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).