Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
1998-02-27
Journal of Statistical Physics 94:5/6 (1999) 739-758
Physics
Condensed Matter
Disordered Systems and Neural Networks
21 pages, 7 figures; to appear in Journal of Statistical Physics (March 1999); this revision contains final version incorporat
Scientific paper
We study the random link traveling salesman problem, where lengths l_ij between city i and city j are taken to be independent, identically distributed random variables. We discuss a theoretical approach, the cavity method, that has been proposed for finding the optimal tour length over this random ensemble, given the assumption of replica symmetry. Using finite size scaling and a renormalized model, we test the cavity predictions against the results of simulations, and find excellent agreement over a range of distributions. We thus provide numerical evidence that the replica symmetric solution to this problem is the correct one. Finally, we note a surprising result concerning the distribution of kth-nearest neighbor links in optimal tours, and invite a theoretical understanding of this phenomenon.
Martin Olivier C.
Percus Allon G.
No associations
LandOfFree
The stochastic traveling salesman problem: Finite size scaling and the cavity prediction 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 stochastic traveling salesman problem: Finite size scaling and the cavity prediction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The stochastic traveling salesman problem: Finite size scaling and the cavity prediction will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-364163