Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem

We consider the Euclidean traveling salesman problem for N cities randomly distributed in the unit d-dimensional hypercube, and investigate the finite size scaling of the mean optimal tour length LE. With toroidal boundary conditions we find, motivated by a remarkable universality in the kth nearest neighbor distribution, that LE(d0ex0ex=0ex0ex2)0ex0ex=0ex0ex(0.7120±0.0002)N1/2[1+O(1/N)] and LE(d0ex0ex=0ex0ex3)0ex0ex=0ex0ex(0.6979±0.0002)N2/3[1+O(1/N)]. We then consider a mean-field approach in the limit N→∞ which we find to be a good approximation (the error being less than 2.1% at d0ex0ex=0ex0ex1,2, and 3), and which suggests that LE(d)0ex0ex=0ex0exN^1-1/d√d/2πe0ex0ex(πd)1/2d[1+O(1/d)] at large d.