Replica Symmetry and Combinatorial Optimization

It is well-known that methods of statistical physics are applicable to computational optimization problems like the traveling salesman problem. In the random link model where all pairs of cities receive independent distances several features of the optimum solution have been predicted non-rigorously based on so-called replica symmetry. I will present a rigorous approach where each of several optimization problems leads to a two-person game. The assumptions underlying the replica symmetric ansatz are essentially equivalent to the statement that the associated game can be effectively analyzed by a game-tree search. This approach has led to proofs of several conjectures originating from the physics community. A paper is available at arXiv:0908.1920.,

#