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

DOI10.1023/A:1004570713967MaRDI QIDQ1308014zbMATH OpenOpenAlexWikidataFDO

Authors Allon G. Percus, O. C. Martin

Publication date 22 November 1999

Published in Journal of Statistical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9802295

zbMATH Keywords

combinatorial optimizationdisordered systemsreplic symmetry

Mathematics Subject Classification ID

Stochastic programming (90C15) Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics (82C31) Dynamics of disordered systems (random Ising systems, etc.) in time-dependent statistical mechanics (82C44)

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 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.

Recommendations

• The mean field traveling salesman and related problems
• On the nearest-neighbor algorithm for the mean-field traveling salesman problem
• Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm
• Random tours in the traveling salesman problem: Analysis and application

Cited in

(11)

• Deterministic walks in random networks: An application to thesaurus graphs
• scientific article; zbMATH DE number 19253 (Why is no real title available?)
• Statistical mechanics methods and phase transitions in optimization problems
• Replica symmetry of the minimum matching
• Fluctuations in the site-disordered traveling salesman problem
• The mean field traveling salesman and related problems
• Traveling Salesman Problem and Statistical Physics
• New global optima results for the Kauffman \(NK\) model: Handling dependency
• The traveling purchaser problem with stochastic prices: exact and approximate algorithms
• The \(\zeta(2)\) limit in the random assignment problem
• Global optima results for the Kauffman \(NK\) model

This page was built for publication: The stochastic traveling salesman problem: finite size scaling and the cavity prediction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1308014)