Replica symmetry of the minimum matching

Pages 1061-1091 from Volume 175 (2012), Issue 3 by Johan Wästlund

Abstract

We establish the soundness of the replica symmetric ansatz introduced by M. Mézard and G. Parisi for the minimum matching problem in the pseudo-dimension $d$ mean field model for $d\geq 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$.

  • [A92] Go to document D. J. Aldous, "Asymptotics in the random assignment problem," Probab. Theory Related Fields, vol. 93, iss. 4, pp. 507-534, 1992.
    @article {A92, MRKEY = {1183889},
      AUTHOR = {Aldous, David J.},
      TITLE = {Asymptotics in the random assignment problem},
      JOURNAL = {Probab. Theory Related Fields},
      FJOURNAL = {Probability Theory and Related Fields},
      VOLUME = {93},
      YEAR = {1992},
      NUMBER = {4},
      PAGES = {507--534},
      ISSN = {0178-8051},
      CODEN = {PTRFEU},
      MRCLASS = {60C05 (05C70 05C80)},
      MRNUMBER = {1183889},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1007/BF01192719},
      ZBLNUMBER = {0767.60006},
      }
  • [A01] Go to document D. J. Aldous, "The $\zeta(2)$ limit in the random assignment problem," Random Structures Algorithms, vol. 18, iss. 4, pp. 381-418, 2001.
    @article {A01, MRKEY = {1839499},
      AUTHOR = {Aldous, David J.},
      TITLE = {The {$\zeta(2)$} limit in the random assignment problem},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {18},
      YEAR = {2001},
      NUMBER = {4},
      PAGES = {381--418},
      ISSN = {1042-9832},
      MRCLASS = {60C05 (60F05)},
      MRNUMBER = {1839499},
      MRREVIEWER = {Aart J. Stam},
      DOI = {10.1002/rsa.1015},
      ZBLNUMBER = {0993.60018},
      }
  • [AB05] Go to document D. J. Aldous and A. Bandyopadhyay, "A survey of max-type recursive distributional equations," Ann. Appl. Probab., vol. 15, iss. 2, pp. 1047-1110, 2005.
    @article {AB05, MRKEY = {2134098},
      AUTHOR = {Aldous, David J. and Bandyopadhyay, Antar},
      TITLE = {A survey of max-type recursive distributional equations},
      JOURNAL = {Ann. Appl. Probab.},
      FJOURNAL = {The Annals of Applied Probability},
      VOLUME = {15},
      YEAR = {2005},
      NUMBER = {2},
      PAGES = {1047--1110},
      ISSN = {1050-5164},
      MRCLASS = {60E05 (62E10 68Q25 68W20 82B44)},
      MRNUMBER = {2134098},
      MRREVIEWER = {Peter Eichelsbacher},
      DOI = {10.1214/105051605000000142},
      ZBLNUMBER = {1105.60012},
      }
  • [ASt03] D. J. Aldous and M. J. Steele, "The objective method: probabilistic combinatorial optimization and local weak convergence," in Probability on Discrete Structures, New York: Springer-Verlag, 2004, vol. 110, pp. 1-72.
    @incollection {ASt03, MRKEY = {2023650},
      AUTHOR = {Aldous, David J. and Steele, J. Michael},
      TITLE = {The objective method: probabilistic combinatorial optimization and local weak convergence},
      BOOKTITLE = {Probability on Discrete Structures},
      SERIES = {Encyclopaedia Math. Sci.},
      VOLUME = {110},
      PAGES = {1--72},
      PUBLISHER = {Springer-Verlag},
      ADDRESS = {New York},
      YEAR = {2004},
      MRCLASS = {60C05 (05C80 60F05)},
      MRNUMBER = {2023650},
      MRREVIEWER = {Ralph Neininger},
      ZBLNUMBER = {1037.60008},
      }
  • [BM89] Go to document S. Bacci and E. N. Miranda, "The traveling salesman problem and its analogy with two-dimensional spin glasses," J. Statist. Phys., vol. 56, iss. 3-4, pp. 547-551, 1989.
    @article {BM89, MRKEY = {1009516},
      AUTHOR = {Bacci, S. and Miranda, E. N.},
      TITLE = {The traveling salesman problem and its analogy with two-dimensional spin glasses},
      JOURNAL = {J. Statist. Phys.},
      FJOURNAL = {Journal of Statistical Physics},
      VOLUME = {56},
      YEAR = {1989},
      NUMBER = {3-4},
      PAGES = {547--551},
      ISSN = {0022-4715},
      CODEN = {JSTPSB},
      MRCLASS = {90B10 (82A57 90C27)},
      MRNUMBER = {1009516},
      DOI = {10.1007/BF01044452},
      }
  • [B06] Go to document A. Bandyopadhyay, "Endogeny for the logistic recursive distributional equation," Z. Anal. Anwend., vol. 30, iss. 2, pp. 237-251, 2011.
    @article {B06, MRKEY = {1009516},
      AUTHOR = {Bandyopadhyay, Antar},
      TITLE = {Endogeny for the logistic recursive distributional equation},
      JOURNAL = {Z. Anal. Anwend.},
      FJOURNAL = {Zeitschrift für Analysis und ihre Anwendungen. Journal of Analysis and its Applications},
      VOLUME = {30},
      YEAR = {2011},
      NUMBER = {2},
      PAGES = {237--251},
      ISSN = {0232-2064},
      MRCLASS = {60E05 (60J80)},
      MRNUMBER = {2793003},
      MRREVIEWER = {Matthias Meiners},
      DOI = {10.4171/ZAA/1433},
      ZBLNUMBER = {1215.60009},
      }
  • [BG08] Go to document A. Bandyopadhyay and D. Gamarnik, "Counting without sampling: asymptotics of the log-partition function for certain statistical physics models," Random Structures Algorithms, vol. 33, iss. 4, pp. 452-479, 2008.
    @article {BG08, MRKEY = {2462251},
      AUTHOR = {Bandyopadhyay, Antar and Gamarnik, David},
      TITLE = {Counting without sampling: asymptotics of the log-partition function for certain statistical physics models},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {33},
      YEAR = {2008},
      NUMBER = {4},
      PAGES = {452--479},
      ISSN = {1042-9832},
      MRCLASS = {68W25 (05A16 05C15 05C80 82B20)},
      MRNUMBER = {2462251},
      MRREVIEWER = {Mark R. Jerrum},
      DOI = {10.1002/rsa.20236},
      ZBLNUMBER = {1157.82006},
      }
  • [BBCZ08] M. Bayati, C. Borgs, J. Chayes, and R. Zecchina, "On the exactness of the cavity method for weighted $b$-matchings on arbitrary graphs and its relation to linear programs," J. Stat. Mech., 2008.
    @article{BBCZ08,
      author={Bayati, M. and Borgs, C. and Chayes, J. and Zecchina, R.},
      TITLE={On the exactness of the cavity method for weighted $b$-matchings on arbitrary graphs and its relation to linear programs},
      JOURNAL={J. Stat. Mech.},
      YEAR={2008},
      }
  • [BHH59] Go to document J. Beardwood, J. H. Halton, and J. M. Hammersley, "The shortest path through many points," Proc. Cambridge Philos. Soc., vol. 55, pp. 299-327, 1959.
    @article {BHH59, MRKEY = {0109316},
      AUTHOR = {Beardwood, Jillian and Halton, J. H. and Hammersley, J. M.},
      TITLE = {The shortest path through many points},
      JOURNAL = {Proc. Cambridge Philos. Soc.},
      VOLUME = {55},
      YEAR = {1959},
      PAGES = {299--327},
      MRCLASS = {52.00 (60.00)},
      MRNUMBER = {0109316},
      MRREVIEWER = {S. J. Taylor},
      ZBLNUMBER = {0118.35601},
      DOI = {10.1017/S0305004100034095},
      }
  • [BP99] Go to document S. Boettcher and A. Percus, "Nature’s way of optimizing," Artificial Intelligence, vol. 119, pp. 275-286, 2000.
    @article{BP99,
      author={Boettcher, S. and Percus, A.},
      TITLE={Nature's way of optimizing},
      JOURNAL={Artificial Intelligence},
      YEAR={2000},
      VOLUME={119},
      PAGES={275--286},
      ZBLNUMBER = {0949.90075},
      DOI = {10.1016/S0004-3702(00)00007-2},
     }
  • [BKMP91] Go to document R. Brunetti, W. Krauth, M. Mézard, and G. Parisi, "Extensive Numerical Simulation of Weighted Matchings: Total Length and Distribution of Links in the Optimal Solution," Europhys. Lett., vol. 14, pp. 295-301, 1991.
    @article{BKMP91,
      author={Brunetti, R. and Krauth, W. and Mézard, M. and Parisi, G.},
      TITLE={Extensive Numerical Simulation of Weighted Matchings: Total Length and Distribution of Links in the Optimal Solution},
      JOURNAL={Europhys. Lett.},
      VOLUME={14},
      YEAR={1991},
      PAGES={295--301},
      DOI = {10.1209/0295-5075/14/4/002},
      }
  • [CBBMP97] Go to document N. J. Cerf, J. Boutet de Monvel, O. Bohigas, O. C. Martin, and A. G. Percus, "The Random Link Approximation for the Euclidean Traveling Salesman Problem," J. de Phys., vol. 7, pp. 117-136, 1997.
    @article{CBBMP97,
      author={Cerf, N. J. and Boutet de Monvel, J. and Bohigas, O. and Martin, O. C. and Percus, A. G.},
      TITLE={The Random Link Approximation for the {E}uclidean Traveling Salesman Problem},
      JOURNAL={J. de Phys.},
      VOLUME={7},
      YEAR={1997},
      PAGES={117--136},
      DOI = {10.1051/jp1:1997129},
      }
  • [DH] Go to document E. D. Demaine and R. A. Hearn, "Constraint logic: a uniform framework for modeling computation as games," in Twenty-Third Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2008, pp. 149-162.
    @incollection {DH, MRKEY = {2513497},
      AUTHOR = {Demaine, Erik D. and Hearn, Robert A.},
      TITLE = {Constraint logic: a uniform framework for modeling computation as games},
      BOOKTITLE = {Twenty-{T}hird {A}nnual {IEEE} {C}onference on {C}omputational {C}omplexity},
      PAGES = {149--162},
      PUBLISHER = {IEEE Computer Soc., Los Alamitos, CA},
      YEAR = {2008},
      MRCLASS = {68Q15 (05C20 68Q05 91A43)},
      MRNUMBER = {2513497},
      DOI = {10.1109/CCC.2008.35},
      }
  • [F85] Go to document A. M. Frieze, "On the value of a random minimum spanning tree problem," Discrete Appl. Math., vol. 10, iss. 1, pp. 47-56, 1985.
    @article {F85, MRKEY = {0770868},
      AUTHOR = {Frieze, A. M.},
      TITLE = {On the value of a random minimum spanning tree problem},
      JOURNAL = {Discrete Appl. Math.},
      FJOURNAL = {Discrete Applied Mathematics. The Journal of Combinatorial Algorithms, Informatics and Computational Sciences},
      VOLUME = {10},
      YEAR = {1985},
      NUMBER = {1},
      PAGES = {47--56},
      ISSN = {0166-218X},
      CODEN = {DAMADU},
      MRCLASS = {05C80 (05C05 60C05)},
      MRNUMBER = {0770868},
      MRREVIEWER = {Micha{\l}Karo{ń}ski},
      DOI = {10.1016/0166-218X(85)90058-7},
      ZBLNUMBER = {0578.05015},
      }
  • [F04] Go to document A. M. Frieze, "On random symmetric travelling salesman problems," Math. Oper. Res., vol. 29, iss. 4, pp. 878-890, 2004.
    @article {F04, MRKEY = {2104159},
      AUTHOR = {Frieze, A. M.},
      TITLE = {On random symmetric travelling salesman problems},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {29},
      YEAR = {2004},
      NUMBER = {4},
      PAGES = {878--890},
      ISSN = {0364-765X},
      MRCLASS = {05C80 (60C05 68W40 90C27 90C59)},
      MRNUMBER = {2104159},
      MRREVIEWER = {Konrad Engel},
      DOI = {10.1287/moor.1040.0105},
      ZBLNUMBER = {1082.05517},
      }
  • [GNS05] Go to document D. Gamarnik, T. Nowicki, and G. Swirszcz, "Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method," Random Structures Algorithms, vol. 28, iss. 1, pp. 76-106, 2006.
    @article {GNS05, MRKEY = {2187483},
      AUTHOR = {Gamarnik, David and Nowicki, Tomasz and Swirszcz, Grzegorz},
      TITLE = {Maximum weight independent sets and matchings in sparse random graphs. {E}xact results using the local weak convergence method},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {28},
      YEAR = {2006},
      NUMBER = {1},
      PAGES = {76--106},
      ISSN = {1042-9832},
      MRCLASS = {05C80 (60C05)},
      MRNUMBER = {2187483},
      MRREVIEWER = {Deryk Osthus},
      DOI = {10.1002/rsa.20072},
      ZBLNUMBER = {1094.05050},
      }
  • [HMM98] Go to document J. Houdayer, J. H. Boutet de Monvel, and O. C. Martin, "Comparing mean field and Euclidean matching problems," Eur. Phys. J. B Condens. Matter Phys., vol. 6, iss. 3, pp. 383-393, 1998.
    @article {HMM98, MRKEY = {1665617},
      AUTHOR = {Houdayer, J. and Boutet de Monvel, J. H. and Martin, O. C.},
      TITLE = {Comparing mean field and {E}uclidean matching problems},
      JOURNAL = {Eur. Phys. J. B Condens. Matter Phys.},
      FJOURNAL = {The European Physical Journal. B. Condensed Matter Physics},
      VOLUME = {6},
      YEAR = {1998},
      NUMBER = {3},
      PAGES = {383--393},
      ISSN = {1434-6028},
      MRCLASS = {82B44 (82D30)},
      MRNUMBER = {1665617},
      DOI = {10.1007/s100510050565},
      }
  • [JLR00] S. Janson, T. Łuczak, and A. Rucinski, Random Graphs, New York: Wiley-Interscience, 2000.
    @book {JLR00, MRKEY = {1782847},
      AUTHOR = {Janson, Svante and {\L}uczak, Tomasz and Rucinski, Andrzej},
      TITLE = {Random Graphs},
      SERIES = {Wiley-Intersci. Ser. Discrete Math. Optim.},
      PUBLISHER = {Wiley-Interscience},
      ADDRESS={New York},
      YEAR = {2000},
      PAGES = {xii+333},
      ISBN = {0-471-17541-2},
      MRCLASS = {05C80 (60C05 82B41)},
      MRNUMBER = {1782847},
      MRREVIEWER = {Mark R. Jerrum},
      ZBLNUMBER = {0968.05003},
      ZBLNUMBER = {0947.05071},
      }
  • [KT85] Go to document S. Kirkpatrick and G. Toulouse, "Configuration space analysis of travelling salesman problems," J. Physique, vol. 46, iss. 8, pp. 1277-1292, 1985.
    @article {KT85, MRKEY = {0807242},
      AUTHOR = {Kirkpatrick, S. and Toulouse, G.},
      TITLE = {Configuration space analysis of travelling salesman problems},
      JOURNAL = {J. Physique},
      FJOURNAL = {Le Journal de Physique},
      VOLUME = {46},
      YEAR = {1985},
      NUMBER = {8},
      PAGES = {1277--1292},
      ISSN = {0302-0738},
      CODEN = {JOPQAG},
      MRCLASS = {82A57 (05C35 90B10)},
      MRNUMBER = {0807242},
      MRREVIEWER = {B. Derrida},
      DOI = {10.1051/jphys:019850046080127700},
      }
  • [KM89] Go to document W. Krauth and M. Mézard, "The Cavity Method and the Travelling-Salesman Problem," Europhys. Lett., vol. 8, pp. 213-218, 1989.
    @article{KM89,
      author={Krauth, W. and Mézard, M.},
      TITLE={The Cavity Method and the Travelling-Salesman Problem},
      JOURNAL={Europhys. Lett.},
      VOLUME={8},
      YEAR={1989},
      PAGES={213--218},
      DOI = {10.1209/0295-5075/8/3/002},
     }
  • [LW04] Go to document S. Linusson and J. Wästlund, "A proof of Parisi’s conjecture on the random assignment problem," Probab. Theory Related Fields, vol. 128, iss. 3, pp. 419-440, 2004.
    @article {LW04, MRKEY = {2036492},
      AUTHOR = {Linusson, Svante and W{ä}stlund, Johan},
      TITLE = {A proof of {P}arisi's conjecture on the random assignment problem},
      JOURNAL = {Probab. Theory Related Fields},
      FJOURNAL = {Probability Theory and Related Fields},
      VOLUME = {128},
      YEAR = {2004},
      NUMBER = {3},
      PAGES = {419--440},
      ISSN = {0178-8051},
      CODEN = {PTRFEU},
      MRCLASS = {90C15 (15A52 60C05)},
      MRNUMBER = {2036492},
      MRREVIEWER = {Giovanni Andreatta},
      DOI = {10.1007/s00440-003-0308-9},
      }
  • [MMR05] Go to document O. C. Martin, M. Mézard, and O. Rivoire, "Random multi-index matching problems," J. Stat. Mech. Theory Exp., iss. 9, p. 09006, 2005.
    @article {MMR05, MRKEY = {2174087},
      AUTHOR = {Martin, O. C. and M{é}zard, M. and Rivoire, O.},
      TITLE = {Random multi-index matching problems},
      JOURNAL = {J. Stat. Mech. Theory Exp.},
      FJOURNAL = {Journal of Statistical Mechanics: Theory and Experiment},
      YEAR = {2005},
      NUMBER = {9},
      PAGES = {P09006, 36 pp.},
      ISSN = {1742-5468},
      MRCLASS = {90B80 (82B44 82D30 90C27)},
      MRNUMBER = {2174087},
      MRREVIEWER = {Menachem Dishon},
      DOI = {10.1088/1742-5468/2005/09/P09006},
     }
  • [MP85] Go to document M. Mézard and G. Parisi, "Replicas and optimization," J. de Phys. Lett., vol. 46, pp. 771-778, 1985.
    @article{MP85,
      author={Mézard, M. and Parisi, G.},
      TITLE={Replicas and optimization},
      JOURNAL={J. de Phys. Lett.},
      VOLUME={46},
      YEAR={1985},
      PAGES={771--778},
      DOI = {10.1051/jphyslet:019850046017077100},
     }
  • [MP86a] Go to document M. Mézard and G. Parisi, "A replica analysis of the travelling salesman problem," J. de Phys., vol. 47, pp. 1285-1296, 1986.
    @article{MP86a,
      author={Mézard, M. and Parisi, G.},
      TITLE={A replica analysis of the travelling salesman problem},
      JOURNAL={J. de Phys.},
      VOLUME={47},
      YEAR={1986},
      PAGES={1285--1296},
      DOI = {10.1051/jphys:019860047080128500},
      }
  • [MP86b] Go to document M. Mézard and G. Parisi, "Mean-field equations for the matching and the travelling salesman problems," Europhys. Lett., vol. 2, pp. 913-918, 1986.
    @article{MP86b,
      author={Mézard, M. and Parisi, G.},
      TITLE={Mean-field equations for the matching and the travelling salesman problems},
      JOURNAL={Europhys. Lett.},
      VOLUME={2},
      YEAR={1986},
      PAGES={913--918},
      DOI = {doi:10.1209/0295-5075/2/12/005},
      }
  • [MP87] Go to document M. Mézard and G. Parisi, "On the solution of the random link matching problems," J. de Phys. Lett., vol. 48, pp. 1451-1459, 1987.
    @article{MP87,
      author={Mézard, M. and Parisi, G.},
      TITLE={On the solution of the random link matching problems},
      JOURNAL={J. de Phys. Lett.},
      VOLUME={48},
      YEAR={1987},
      PAGES={1451--1459},
      DOI = {10.1051/jphys:019870048090145100},
     }
  • [MPV87] M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond, Teaneck, NJ: World Scientific Publishing Co., 1987, vol. 9.
    @book {MPV87, MRKEY = {1026102},
      AUTHOR = {M{é}zard, M. and Parisi, Giorgio and Virasoro, Miguel Angel},
      TITLE = {Spin Glass Theory and Beyond},
      SERIES = {World Sci. Lecture Notes Phys.},
      VOLUME = {9},
      PUBLISHER = {World Scientific Publishing Co.},
      ADDRESS = {Teaneck, NJ},
      YEAR = {1987},
      PAGES = {xiv+461},
      ISBN = {9971-50-115-5; 9971-50-116-3},
      MRCLASS = {82D30 (68T01 82-02 82C32 92B20)},
      MRNUMBER = {1026102},
      MRREVIEWER = {Aernout C. D. van Enter},
      ZBLNUMBER = {0992.82500},
      }
  • [MPZ02] Go to document M. Mézard, G. Parisi, and R. Zecchina, "Analytic and Algorithmic Solution of Random Satisfiability Problems," Science, vol. 297, pp. 812-815, 2002.
    @article{MPZ02,
      author={Mézard, M. and Parisi, G. and Zecchina, R.},
      TITLE={Analytic and Algorithmic Solution of Random Satisfiability Problems},
      JOURNAL={Science},
      VOLUME={297},
      YEAR={2002},
      PAGES={812--815},
      DOI = {10.1126/science.1073287},
      }
  • [NPS05] Go to document C. Nair, B. Prabhakar, and M. Sharma, "Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures," Random Structures Algorithms, vol. 27, iss. 4, pp. 413-444, 2005.
    @article {NPS05, MRKEY = {2178256},
      AUTHOR = {Nair, Chandra and Prabhakar, Balaji and Sharma, Mayank},
      TITLE = {Proofs of the {P}arisi and {C}oppersmith-{S}orkin random assignment conjectures},
      JOURNAL = {Random Structures Algorithms},
      FJOURNAL = {Random Structures \& Algorithms},
      VOLUME = {27},
      YEAR = {2005},
      NUMBER = {4},
      PAGES = {413--444},
      ISSN = {1042-9832},
      MRCLASS = {90B36 (05C70 90B50)},
      MRNUMBER = {2178256},
      DOI = {10.1002/rsa.20084},
      ZBLNUMBER = {1125.90026},
      }
  • [PPR03] Go to document A. Pagnani, G. Parisi, and M. Ratieville, "Near-optimal configurations in mean-field disordered systems," Phys. Rev. E, vol. 68, p. 046706, 2003.
    @article{PPR03,
      author={Pagnani, A. and Parisi, G. and Ratieville, M.},
      TITLE={Near-optimal configurations in mean-field disordered systems},
      JOURNAL={Phys. Rev. E},
      VOLUME={68},
      YEAR={2003},
      DOI = {10.1103/PhysRevE.68.046706},
      PAGES={046706},
     }
  • [P80] Go to document G. Parisi, "A sequence of approximated solutions to the S-K model for spin glasses," J. Phys. A, vol. 13, p. 115, 1980.
    @article{P80,
      author={Parisi, G.},
      TITLE={A sequence of approximated solutions to the {S}-{K} model for spin glasses},
      JOURNAL={J. Phys. A},
      VOLUME={13},
      YEAR={1980},
      PAGES={L115},
      DOI = {10.1088/0305-4470/13/4/009},
     }
  • [P86] G. Parisi, "Spin glasses and optimization problems without replicas," in Le Hasard et la Matière/Chance and Matter, Souletie, J., Vannimenus, J., and Stora, R., Eds., Netherlands: Elsevier Science Publishers B. V., 1987, pp. 525-552.
    @incollection {P86, MRKEY = {0985792},
      AUTHOR = {Parisi, G.},
      TITLE = {Spin glasses and optimization problems without replicas},
      BOOKTITLE = {Le Hasard et la Matière/Chance and Matter},
      VENUE={{L}es {H}ouches, 1986},
      EDITOR={Souletie, J. and Vannimenus, J. and Stora, R.},
      PAGES = {525--552},
      PUBLISHER = {Elsevier Science Publishers B. V.},
      ADDRESS = {Netherlands},
      YEAR = {1987},
      MRCLASS = {82A57 (82A51 90C27)},
      MRNUMBER = {0985792},
      }
  • [PR01] Go to document G. Parisi and M. Ratiéville, "Neighborhood preferences in random matching problems," Euro. Phys. J. B, vol. 22, pp. 229-237, 2001.
    @article{PR01,
      author={Parisi, G. and Ratiéville, M.},
      TITLE={Neighborhood preferences in random matching problems},
      JOURNAL={Euro. Phys. J. B},
      VOLUME={22},
      YEAR={2001},
      PAGES={229--237},
      DOI = {10.1007/PL00011144},
      }
  • [PW] G. Parisi and J. Wästlund, Mean field matching and traveling salesman in pseudo-dimension 1.
    @misc{PW,
      author={Parisi, G. and Wästlund, J.},
      TITLE={Mean field matching and {traveling salesman} in pseudo-dimension 1},
      NOTE={manuscript},
     }
  • [P97] A. G. Percus, Voyageur de commerce et problèmes stochastiques associés, 1997.
    @misc{P97,
      author={Percus, Allon G.},
      TITLE={Voyageur de commerce et problèmes stochastiques associés},
      NOTE={Ph.D. thesis, Université Pierre et Marie Curie, Paris},
      YEAR={1997},
     }
  • [PM98] Go to document A. G. Percus and O. C. Martin, "The stochastic traveling salesman problem: finite size scaling and the cavity prediction," J. Statist. Phys., vol. 94, iss. 5-6, pp. 739-758, 1999.
    @article {PM98, MRKEY = {1694076},
      AUTHOR = {Percus, Allon G. and Martin, Olivier C.},
      TITLE = {The stochastic traveling salesman problem: finite size scaling and the cavity prediction},
      JOURNAL = {J. Statist. Phys.},
      FJOURNAL = {Journal of Statistical Physics},
      VOLUME = {94},
      YEAR = {1999},
      NUMBER = {5-6},
      PAGES = {739--758},
      ISSN = {0022-4715},
      CODEN = {JSTPSB},
      MRCLASS = {82C31 (82C44 90C15)},
      MRNUMBER = {1694076},
      DOI = {10.1023/A:1004570713967},
      ZBLNUMBER = {0963.82035},
      }
  • [SS09] Go to document J. Salez and D. Shah, Optimality of Belief Propagation for Random Assignment Problem, Philadelphia, PA: Society for Industrial and Applied Mathematics, 2009.
    @book{SS09,
      author={Salez, Justin and Shah, Devavrat},
      TITLE={Optimality of Belief Propagation for Random Assignment Problem},
      JOURNAL={Proc. SODA},
      YEAR={2009},
      PUBLISHER={Society for Industrial and Applied Mathematics},
      NOTE= {187--196},
      ADDRESS={Philadelphia, PA},
      URL={http://www.informatik.uni-trier.de/~ley/db/conf/soda/soda2009.html#SalezS09},
      }
  • [SS09b] Go to document J. Salez and D. Shah, "Belief propagation: an asymptotically optimal algorithm for the random assignment problem," Math. Oper. Res., vol. 34, iss. 2, pp. 468-480, 2009.
    @article {SS09b, MRKEY = {2554069},
      AUTHOR = {Salez, Justin and Shah, Devavrat},
      TITLE = {Belief propagation: an asymptotically optimal algorithm for the random assignment problem},
      JOURNAL = {Math. Oper. Res.},
      FJOURNAL = {Mathematics of Operations Research},
      VOLUME = {34},
      YEAR = {2009},
      NUMBER = {2},
      PAGES = {468--480},
      ISSN = {0364-765X},
      MRCLASS = {68W40 (05C70 05C80 60C05 68T20)},
      MRNUMBER = {2554069},
      MRREVIEWER = {Raphael Yuster},
      DOI = {10.1287/moor.1090.0380},
      ZBLNUMBER = {05881643},
      }
  • [SK75] Go to document D. Sherrington and S. Kirkpatrick, "Solvable model of a spin glass," Phys. Rev. Lett., vol. 35, pp. 1792-1796, 1975.
    @article{SK75,
      author={Sherrington, D. and Kirkpatrick, S.},
      TITLE={Solvable model of a spin glass},
      JOURNAL={Phys. Rev. Lett.},
      VOLUME={35},
      YEAR={1975},
      PAGES={1792--1796},
      DOI = {10.1103/PhysRevLett.35.1792},
     }
  • [S86] Go to document N. Sourlas, "Statistical Mechanics and the Travelling Salesman Problem," Europhys. Lett., vol. 2, pp. 919-923, 1986.
    @article{S86,
      author={Sourlas, N.},
      TITLE={Statistical Mechanics and the Travelling Salesman Problem},
      JOURNAL={Europhys. Lett.},
      VOLUME={2},
      YEAR={1986},
      PAGES={919--923},
      DOI = {10.1209/0295-5075/2/12/006},
     }
  • [T06] Go to document M. Talagrand, "The Parisi formula," Ann. of Math., vol. 163, iss. 1, pp. 221-263, 2006.
    @article {T06, MRKEY = {2195134},
      AUTHOR = {Talagrand, Michel},
      TITLE = {The {P}arisi formula},
      JOURNAL = {Ann. of Math.},
      FJOURNAL = {Annals of Mathematics. Second Series},
      VOLUME = {163},
      YEAR = {2006},
      NUMBER = {1},
      PAGES = {221--263},
      ISSN = {0003-486X},
      CODEN = {ANMAAH},
      MRCLASS = {82B44 (82D30)},
      MRNUMBER = {2195134},
      MRREVIEWER = {Fran{ç}ois Germinet},
      DOI = {10.4007/annals.2006.163.221},
      ZBLNUMBER = {1137.82010},
      }
  • [Weasy] Go to document J. Wästlund, "An easy proof of the $\zeta(2)$ limit in the random assignment problem," Electron. Commun. Probab., vol. 14, pp. 261-269, 2009.
    @article {Weasy, MRKEY = {2516261},
      AUTHOR = {W{ä}stlund, Johan},
      TITLE = {An easy proof of the {$\zeta(2)$} limit in the random assignment problem},
      JOURNAL = {Electron. Commun. Probab.},
      FJOURNAL = {Electronic Communications in Probability},
      VOLUME = {14},
      YEAR = {2009},
      PAGES = {261--269},
      ISSN = {1083-589X},
      MRCLASS = {05C80 (90C27 90C35)},
      MRNUMBER = {2516261},
      ZBLNUMBER = {1195.60018},
      DOI={10.1214/ECP.v14-1475},
      }
  • [W10] Go to document J. Wästlund, "The mean field traveling salesman and related problems," Acta Math., vol. 204, iss. 1, pp. 91-150, 2010.
    @article {W10, MRKEY = {2600434},
      AUTHOR = {W{ä}stlund, Johan},
      TITLE = {The mean field traveling salesman and related problems},
      JOURNAL = {Acta Math.},
      FJOURNAL = {Acta Mathematica},
      VOLUME = {204},
      YEAR = {2010},
      NUMBER = {1},
      PAGES = {91--150},
      ISSN = {0001-5962},
      CODEN = {ACMAA8},
      MRCLASS = {90B15 (05C80 05C90 60C05 60F10 82B44 90C27)},
      MRNUMBER = {2600434},
      MRREVIEWER = {Yukihiro Maruyama},
      DOI = {10.1007/s11511-010-0046-7},
      ZBLNUMBER = {1231.90370},
     }
  • [W06] Go to document D. Weitz, "Counting independent sets up to the tree threshold," in STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, New York: ACM, 2006, pp. 140-149.
    @incollection {W06, MRKEY = {2277139},
      AUTHOR = {Weitz, Dror},
      TITLE = {Counting independent sets up to the tree threshold},
      BOOKTITLE = {S{TOC}'06: {P}roceedings of the 38th {A}nnual {ACM} {S}ymposium on {T}heory of {C}omputing},
      PAGES = {140--149},
      PUBLISHER = {ACM},
      ADDRESS = {New York},
      YEAR = {2006},
      MRCLASS = {68W25 (05C30 05C69 05C85 68R10 82B05 82C20)},
      MRNUMBER = {2277139},
      DOI = {10.1145/1132516.1132538},
      }

Keywords
, , , , ,
DOI
10.4007/annals.2012.175.3.2
MR
2912702
Zbl
06051267
Milestones
Received: 1 July 2009
Revised: 9 May 2011
Accepted: 3 June 2011
Published online: 1 May 2012

Authors

Johan Wästlund

Department of Mathematical Sciences
Chalmers University of Technology and Gothenburg University
SE-412 96 Gothenburg
Sweden