Random multi-index matching problems. (English) Zbl 1456.91074
Summary: The multi-index matching problem generalizes the well known matching problem by going from pairs to \(d\)-uplets. We use the cavity method from statistical physics to analyse its properties when the costs of the \(d\)-uplets are random. At low temperatures we find for \(d \geq 3\) a frozen glassy phase with vanishing entropy. We also investigate some properties of small samples by enumerating the lowest cost matchings to compare with our theoretical predictions.
MSC:
| 91B80 | Applications of statistical and quantum mechanics to economics (econophysics) |
| 82B44 | Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics |
| 82D30 | Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) |
| 90C27 | Combinatorial optimization |
References:
| [1] | Mézard M and Parisi G 1985 J. Physique46 L771 · doi:10.1051/jphys:019850046080129300 |
| [2] | Mézard M and Parisi G 1986 Europhys. Lett.2 913 |
| [3] | Aldous D J 2001 Random Struct. Algorithms18 381 · Zbl 0993.60018 · doi:10.1002/rsa.1015 |
| [4] | Mulet R, Pagnani A, Weigt M and Zecchina R 2002 Phys. Rev. Lett.89 268701 · Zbl 1267.05121 · doi:10.1103/PhysRevLett.89.268701 |
| [5] | Mézard M and Zecchina R 2002 Phys. Rev. E 66 056126 · doi:10.1103/PhysRevE.66.056126 |
| [6] | Mézard M, Parisi G and Zecchina R 2002 Science297 812 · doi:10.1126/science.1073287 |
| [7] | Martin O C, Mézard M and Rivoire O 2004 Phys. Rev. Lett.93 217205 · doi:10.1103/PhysRevLett.93.217205 |
| [8] | Mézard M, Parisi G and Virasoro M A 1987 Spin-Glass Theory and Beyond(Lecture Notes in Physics vol 9) (Singapore: World Scientific) · Zbl 0992.82500 |
| [9] | Mézard M and Parisi G 1987 J. Physique48 1451 · doi:10.1051/jphys:019870048090145100 |
| [10] | Parisi G and Ratiéville M 2002 Eur. J. Phys. B 29 4 · doi:10.1140/epjb/e2002-00326-3 |
| [11] | Parisi G and Ratiéville M 2001 Eur. J. Phys. B 22 229 · doi:10.1007/PL00011144 |
| [12] | Houdayer J, Boutet de Monvel J H and Martin O C 1998 Eur. Phys. J. B 6 383 · doi:10.1007/s100510050565 |
| [13] | Aldous D and Steele M 2003 Encyclopedia of Mathematical Sciences vol 110 ed H Kesten (Berlin: Springer) pp 1-72 |
| [14] | Linusson S and Wastlund J 2003 Preprint math.CO/0303214 |
| [15] | Nair B P C and Sharma M 2003 available at http://www.stanford.edu/∼balaji/rap.html |
| [16] | Parisi G 1998 Preprint cond-mat/9801176 |
| [17] | Talagrand M 2003 Spin Glasses: A challenge for Mathematicians (Berlin: Springer) · Zbl 1033.82002 |
| [18] | Pierskalla W P 1968 Oper. Res.16 422 · Zbl 0164.50003 · doi:10.1287/opre.16.2.422 |
| [19] | Spieksma F C R 2000 Nonlinear Assignment Problems, Algorithms and Applications ed L Pitsoulis and P Pardalos (Dordrecht: Kluwer) pp 1-12 · Zbl 1029.90036 · doi:10.1007/978-1-4757-3155-2_1 |
| [20] | Burkard R E 2002 Discrete Appl. Math.123 257 · Zbl 1036.90056 · doi:10.1016/S0166-218X(01)00343-2 |
| [21] | Poore A B 1994 Comput. Opt. Appl.3 27 · Zbl 0818.93070 · doi:10.1007/BF01299390 |
| [22] | Pusztaszeri J, Rensing P E and Liebling T M 1995 J. Global Optim.16 422 |
| [23] | Karp R 1972 Complexity of Computer Computations ed R Miller and J Thatcher (New York: Plenum) pp 85-103 · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [24] | Papadimitriou C H and Steiglitz K 1982 Combinatorial Optimization: Algorithms and Complexity (Englewood Cliffs, NJ: Prentice-Hall) · Zbl 0503.90060 |
| [25] | Vannimenus J and Mézard M 1984 J. Physique Lett.45 L1145 · doi:10.1051/jphyslet:0198400450240114500 |
| [26] | Aldous D J 1990 Random Struct. Algorithms1 383 · Zbl 0747.05077 · doi:10.1002/rsa.3240010402 |
| [27] | Mézard M and Parisi G 2001 Eur. Phys. J. B 20 217 · doi:10.1007/PL00011099 |
| [28] | Mézard M and Parisi G 2003 J. Stat. Phys.111 1 · Zbl 1014.82032 · doi:10.1023/A:1022221005097 |
| [29] | Aldous D J and Bandyopadhyay A 2004 Preprint math.PR/0401388 |
| [30] | Montanari A and Ricci-Tersenghi F 2003 Eur. Phys. J. B 33 339 · doi:10.1140/epjb/e2003-00174-7 |
| [31] | Rivoire O, Biroli G, Martin O C and Mézard M 2004 Eur. Phys. J. B 37 55 · doi:10.1140/epjb/e2004-00030-4 |
| [32] | Monasson R 1995 Phys. Rev. Lett.75 2847 · doi:10.1103/PhysRevLett.75.2847 |
| [33] | Derrida B 1980 Phys. Rev. Lett.45 79 · doi:10.1103/PhysRevLett.45.79 |
| [34] | Derrida B and Spohn H 1988 J. Stat. Phys.51 817 · Zbl 1036.82522 · doi:10.1007/BF01014886 |
| [35] | Krauth W and Mézard M 1989 Europhys. Lett.8 213 |
| [36] | Barkai E and Kanter I 1991 Europhys. Lett.14 107 |
| [37] | Mézard M, Ricci-Tersenghi F and Zecchina R 2003 J. Stat. Phys.111 505 · Zbl 1049.82073 · doi:10.1023/A:1022886412117 |
| [38] | Montanari A 2001 Eur. Phys. J. B 23 121 · doi:10.1007/s100510170089 |
| [39] | Gross D J, Kanter I and Sompolinsky H 1985 Phys. Rev. Lett.55 304 · doi:10.1103/PhysRevLett.55.304 |
| [40] | Mertens S, Mézard M and Zecchina R 2003 Preprint cs.CC/0309020 |
| [41] | Rivoire O 2005 PhD Thesis Université Paris-Sud |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
