On random symmetric travelling salesman problems

被引：22

作者：

Frieze, A ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2004年 / 29卷 / 04期

关键词：

travelling salesman; probabilistic analysis;

D O I：

10.1287/moor.1040.0105

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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

引用

页码：878 / 890

页数：13

共 14 条

[1] The ζ(2) limit in the random assignment problem [J].