Replica Symmetry and Combinatorial Optimization

2009/08/13 by Johan Wästlund, Wästlund, Johan
Mathematics · #60C05 #82B44 #90C35 #91A43 #FOS: Mathematics #Probability (math.PR) #math.PR #msc:60C05 #msc:82B44 #msc:90C35 #msc:91A43

paper · pdf · doi:10.48550/arxiv.0908.1920

34 pages. v2: 40 pages. Added a section on "edge cover", example in the introduction, redefined beta_M (changed by a factor 2)

arxiv created 2009/12/01 · arxiv updated 2009/12/08

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≥ 1. The case d=1 of minimum matching corresponds to the pi²/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.

Related

• An interacting replica approach applied to the traveling salesman problem
• Mean field matching and TSP in pseudo-dimension 1
• Random Combinatorial Optimization Problems: Mean Field and Finite-Dimensional Results
• One more discussion of the replica trick: the examples of exact solutions
• The Mezard-Parisi equation for matchings in pseudo-dimension d>1