THE RANDOM LINK APPROXIMATION FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

The traveling salesman problem (TSP) consists of finding the length of the shortest closed tour visiting N ''cities''. We consider the Eucli dean TSP where the cities are distributed randomly and independently i n a d-dimensional unit hypercube. Working with periodic boundary condi tions and inspired by a remarkable universality in the kth nearest nei ghbor distribution, we find for the average optimum tour length [L(E)] = beta(E)(d) N-1-1/d [1 + O(1/N)] with beta(E)(2) = 0.7120 +/- 0.0002 and beta(E)(3) = 0.6979 +/- 0.0002. We then derive analytical predict ions for these quantities using the random link approximation, where t he lengths between cities are taken as independent random variables. F rom the ''cavity'' equations developed by Krauth, Mezard and Parisi, w e calculate the associated random link values beta(RL)(d) For d = 1, 2 , 3, numerical results show that the random link approximation is a go od one, with a discrepancy of less than 2.1% between beta(E)(d) and be ta(RL)(d) For large d, we argue that the approximation is exact up to O(1/d(2)) and give a conjecture for beta(E)(d), in terms of a power se ries in lid, specifying both leading and subleading coefficients.