On random symmetric travelling salesman problems
On random symmetric travelling salesman problems
复制标题
关于随机对称旅行商问题
DOI：
10.1109/sfcs.2002.1182004
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
A. Frieze
中科院分区：
文献类型：
--
作者：
A. Frieze
让完整图K/ sub N/的边缘分配独立统一[0,1]随机边缘。令z/ sub tsp/和z/ sub 2fac/分别为最小长度旅行者旅行和最小权重2因子的权重。我们表明WHP/SUP 1/| Z/SUB TSP/-Z/SUB 2FAC/| =（1）。证明是通过分析多项式时间算法的分析，该算法发现游览仅比z/sub 2fac/更长。
Let the edges of the complete graph K/sub n/ be assigned independent uniform [0,1] random edge weights. Let Z/sub TSP/ and Z/sub 2FAC/ be the weights of the minimum length travelling salesman tour and minimum weight 2-factor respectively. We show that whp/sup 1/ |Z/sub TSP/-Z/sub 2FAC/|=(1). The proof is via the analysis of a polynomial time algorithm that finds a tour only a little longer than Z/sub 2FAC/.