The Stochastic Traveling Salesman Problem: Finite Size Scaling and the Cavity Prediction |
| |
Authors: | Percus Allon G Martin Olivier C |
| |
Institution: | (1) Los Alamos National Laboratory, CIC-3 and Center for Nonlinear Studies, MS-B258, Los Alamos, New Mexico, 87545;(2) Division de Physique Théorique, Institut de Physique Nucléaire, Université Paris-Sud, F-91406 Orsay Cedex, France |
| |
Abstract: | 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 optimum 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 k th-nearest neighbor links in optimal tours, and invite a theoretical understanding of this phenomenon. |
| |
Keywords: | disordered systems combinatorial optimization replica symmetry |
本文献已被 SpringerLink 等数据库收录! |
|