The Random Link Approximation for the Euclidean Traveling Salesman Problem
Nicolas J. Cerf, Jacques Boutet de Monvel, O. Bohigas, Olivier Martin, Allon G. Percus · Journal de Physique I · 1997
. --- 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 kth nearest neighbor distribution, we find for the average optimum tour length hLEi = fi E(d) N 1\\Gamma1=d [1 +O(1=N )] with fi E(2) = 0:7120 \\Sigma 0:0002 and fi E(3) = 0:6979 \\Sigma 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 fi 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 fi E(d) and fi RL(d). For large d,...