On the Exact Solution of Random Travelling Salesman Problems with Medium Size Integer Coefficients
ALAN M. FRIEZE · SIAM Journal on Computing · 1987
Let edge weights for the complete graph on vertex set $\{ 1,2, \cdots ,n\} $ be chosen independently and uniformly from $\{ 0,1, \cdots ,B(n) - 1\} $ where $B(n) = o({n / {\log \log n}})$. We show that there exists a polynomial time $(O(n^3 \log n))$ algorithm which solves the associated travelling salesman problem with probability tending to 1 as n tends to $\infty $.