Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
arXiv:1806.08681 · doi:10.1103/PhysRevE.100.032135
Abstract
We study the energy landscape of the Traveling Salesperson problem (TSP) using exact ground states and a novel linear programming approach to generate excited states with closely defined properties. We look at four different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field-like (1,2)-TSP, which has its origin directly in the mapping of the Hamiltonian circuit problem on the TSP. Our data supports previous conjectures that the Euclidean TSP does not show signatures of replica symmetry breaking neither in two nor in higher dimension. On the other hand the (1,2)-TSP exhibits some signature which does not exclude broken replica symmetry, making it a candidate for further studies in the future.
arXiv comment9 pages, 5 figures, 2 table
References in corpus (22)
- Statistical mechanics of the random K-SAT model
- Nature of the Spin Glass State
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- Study of the de Almeida-Thouless line using power-law diluted one-dimensional Ising spin glasses
- Probing the Almeida-Thouless line away from the mean-field model
- Disappearance of the de Almeida-Thouless line in six dimensions
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Domain-Wall Energies and Magnetization of the Two-Dimensional Random-Bond Ising Model
- Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
- The stochastic traveling salesman problem: Finite size scaling and the cavity prediction
- Statistical mechanics of the vertex-cover problem
- Spin Domains Generate Hierarchical Ground State Structure in J=+/-1 Spin Glasses
- Clustering analysis of the ground-state structure of the vertex-cover problem
- The random link approximation for the Euclidean traveling salesman problem
- Spin Glasses: Still Complex After All These Years?
- The traveling salesman problem, conformal invariance, and dense polymers
- First excitations in two- and three-dimensional random-field Ising systems
- Phase transition for cutting-plane approach to vertex-cover problem
- Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
- Solution-space structure of (some) optimization problems
- Low-energy excitations in the three-dimensional random-field Ising model
- Exact Ground States of the Kaya-Berker Model