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 Euclidean TSP where the cities are distributed randomly and independently in a $d$-dimensional unit hypercube. Working with periodic boundary conditions and inspired by a remarkable universality in the $k$th nearest neighbor distribution, we find for the average optimum tour length $\langle L_E\rangle = \beta_E(d)\,N^{1-1/d}\,[1+O(1/N)]$ with $\beta_E(2)=0.7120 \pm 0.0002$ and $\beta_E(3)=0.6979 \pm 0.0002$. We then derive analytical predictions for these quantities using the random link approximation, where the lengths between cities are taken as independent random variables. {}From the ``cavity'' equations developed by Krauth, M\'ezard and Parisi, we calculate the associated random link values $\beta_{RL}(d)$. For $d=1,2,3$, numerical results show that the random link approximation is a good one, with a discrepancy of less than 2.1\% between $\beta_E(d)$ and $\beta_{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 series in $1/d$, specifying both leading and subleading coefficients.