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 $L_E$. With toroidal boundary conditions we find, motivated by a remarkable universality in the $k$th nearest neighbor distribution, that $L_E(d=2\mathrm{})=(0.7120\pm 0.0002)N^{1/2}[1+O(1/N\left)\right]$ and $L_E(d=3\mathrm{})=(0.6979\pm 0.0002)N^{2/3}[1+O(1/N\left)\right]$. We then consider a mean-field approach in the limit $N\to \infty$ which we find to be a good approximation (the error being less than 2.1% at $d=1,2\mathrm{}$, and 3), and which suggests that $L_E\left(d\right){=N}^{1-1/d}\sqrt{d/2\pi e}\left(\pi d{)}^{1/2d}\right[1+O\left(1/d\right)]$ at large $d$.