Replica symmetry of the minimum matching

• 成果类型: Article
• 署名作者: Wastlund, Johan
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2012.175.3.2
• 发表日期: 2012
• 页码: 1061-1091
• 关键词: traveling salesman problem; Mean-field; zeta(2) limit; asymptotics; parisi; PROOF; MODEL

摘要

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.