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

DOI10.1023/A:1004570713967zbMATH Open0963.82035arXivcond-mat/9802295OpenAlexW2151409764WikidataQ120693794 ScholiaQ120693794MaRDI QIDQ1308014FDOQ1308014

Authors: Allon G. Percus, O. C. Martin 

Publication date: 22 November 1999

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

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.

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

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

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)

Cited In (11)

• Title not available (Why is that?)
• Statistical mechanics methods and phase transitions in optimization problems
• Fluctuations in the site-disordered traveling salesman problem
• Replica symmetry of the minimum matching
• 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
• Deterministic walks in random networks: An application to thesaurus graphs

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)