FINITE-SIZE AND DIMENSIONAL DEPENDENCE IN THE EUCLIDEAN TRAVELING SALESMAN PROBLEM

We consider the Euclidean traveling salesman problem for N cities rand omly distributed in the unit d-dimensional hypercube, and investigate the finite size scaling of the mean optimal tour length L(E). With tor oidal boundary conditions we find, movtivated by a remarkable universa lity in the kth nearest neighbor distribution, that L(E)(d = 2) = (0.7 120 +/- 0.0002) N-1/2 [1 O +(1/N)] and L(E) (d = 3) = 0.6979 +/- 0.000 2) N-2/3 [1 + O(1/N)]. We then consider a mean-field approach in the l imit N --> infinity which we find to be a good approximation (the erro r being less than 2.1 % at d = 1, 2, and 3), and which suggests that L (E)(d) = N-1-1/d root d/2 pi e (pi d)(1/2d)[1 + O(1/d)] at large d.