The random link approximation for the Euclidean traveling salesman problem

Details The random link approximation for the Euclidean traveling salesman problem The random link approximation for the Euclidean traveling salesman problem

1996-07-11

arxiv.org/abs/cond-mat/9607080v2

Journal de Physique I 7:1 (1997) 117-136

Physics

Condensed Matter

29 pages, 6 figures; formatting and typos corrected

Scientific paper

10.1051/jp1:1997129

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 = beta_E(d) N^{1-1/d} [1+O(1/N)] with beta_E(2) = 0.7120 +- 0.0002 and beta_E(3) = 0.6979 +- 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, Mezard 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.

Affiliated with

Also associated with

No associations

Rating

The random link approximation for the Euclidean traveling salesman problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The random link approximation for the Euclidean traveling salesman problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The random link approximation for the Euclidean traveling salesman problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-65205