On the exact solution of random travelling salesman problems with medium size integer coefficients
作者： A. M. Frieze
DOI: 10.1137/0216068
关键词:
摘要: Let edge weights for the complete graph on vertex set $\{ 1,2, \cdots ,n\} $ be chosen independently and uniformly from 0,1, ,B(n) - 1\} where $B(n) = o({n / {\log \log n}})$. We show that there exists a polynomial time $(O(n^3 n))$ algorithm which solves associated travelling salesman problem with probability tending to 1 as n tends $\infty $.
sci-hub.se 参考文章(0)