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.
Speaker Details
Johan Wastlund is a senior researcher at Chalmers University of Technology, Gothenburg, Sweden, and will be visiting the theory group for two weeks. His main field of research is probability, in particular optimization problems in random models, and their connections to computer science and statistical physics.
- Date:
- Speakers:
- Johan Wastlund
- Affiliation:
- Chalmers University of Technology, Gothenburg
-
-
Jeff Running
-
