Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
share
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. We look at some different ensembles, notably the classic finite dimensional Euclidean TSP and the mean-field (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 a signature of broken replica symmetry.
READ FULL TEXT