Replica symmetry of the minimum matching

• We establish the soundness of the replica symmetric ansatz introduced by M. Mezard and G. Parisi for the minimum matching problem in the pseudo-dimension d mean field model for d >= 1. The case d = 1 corresponds to the pi(2)/6-limit for the assignment problem proved by D. Aldous in 2001. We introduce a game-theoretical framework by which we establish the analogous limit also for d > 1.

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

traveling-salesman problem

random assignment problem

local

weak-convergence

mean-field

zeta(2) limit

spin-glasses

asymptotics

equations

parisi

proof

zeta(2) limit

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)