Replica Symmetry and Combinatorial Optimization

Details Replica Symmetry and Combinatorial Optimization Replica Symmetry and Combinatorial Optimization

2009-08-13

arxiv.org/abs/0908.1920v2

Mathematics

Probability

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

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Replica Symmetry and Combinatorial Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Replica Symmetry and Combinatorial Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replica Symmetry and Combinatorial Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-701498