Replica symmetry and replica symmetry breaking for the traveling salesperson problem
Related Experiment Video
Updated: Jan 5, 2026

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
Published on: March 18, 2019
Hendrik Schawe1, Jitesh Kumar Jha1,2, Alexander K Hartmann1
1Institut für Physik, Universität Oldenburg, D-26111 Oldenburg, Germany.
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.
More Related Videos
11:09RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
Published on: July 17, 2021
06:35Construction and Systematical Symmetric Studies of a Series of Supramolecular Clusters with Binary or Ternary Ammonium Triphenylacetates
Published on: February 15, 2016
Related Concept Videos
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Symmetry
Stability of Equilibrium Configuration: Problem Solving
Problem-solving in the context of the stability of equilibrium configuration...
Symmetric Member in Bending
Gauss's Law: Planar Symmetry
Second Uniqueness Theorem
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the surface...