The stochastic traveling salesman problem: Finite size scaling and the cavity prediction

We study the random link traveling salesman problem, where lengths l(ij) be tween city i and city j are taken to be independent, identically distribute d random variables. We discuss a theoretical approach, the cavity method, t hat has been proposed for finding the optimum tour length over this random ensemble, given the assumption of replica symmetry. Using finite size scali ng and a renormalized model, we test the cavity predictions against the res ults of simulations, and find excellent agreement over a range of distribut ions. We thus provide numerical evidence that the replica symmetric solutio n to this problem is the correct one. Finally, we note a surprising result concerning the distribution of k th-nearest neighbor links in optimal tours , and invite a theoretical understanding of this phenomenon.