Replica Symmetry and Combinatorial Optimization
arXiv:0908.1920
Abstract
We establish the soundness of the replica symmetric ansatz introduced by M. Mezard and G. Parisi for minimum matching and the traveling salesman problem in the pseudo-dimension d mean field model for d\geq 1. The case d=1 of minimum matching corresponds to the pi^2/6 limit for the assignment problem established by D. Aldous in 2001, and the analogous limit for the d=1 case of TSP was recently established by the author with a different method. We introduce a game-theoretical framework by which we prove the correctness of the replica-cavity prediction of the corresponding limits also for d>1.
34 pages. v2: 40 pages. Added a section on "edge cover", example in the introduction, redefined beta_M (changed by a factor 2)
References in corpus (6)
- A survey of max-type recursive distributional equations
- On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
- Scaling and Universality in Continuous Length Combinatorial Optimization
- Near optimal configurations in mean field disordered systems
- Percolation-like Scaling Exponents for Minimal Paths and Trees in the Stochastic Mean Field Model
- Constraint Optimization and Statistical Mechanics