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]
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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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},
}
Print version