Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem

Hendrik Schawe, Jitesh Kumar Jha, Alexander K. Hartmann

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 d…