Random multi-index matching problems

DOI10.1088/1742-5468/2005/09/P09006MaRDI QIDQ4968882zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 9 July 2019

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0507180

zbMATH Keywords

cavity and replica methodtypical-case computational complexity

Mathematics Subject Classification ID

Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30) Combinatorial optimization (90C27) Applications of statistical and quantum mechanics to economics (econophysics) (91B80)

Abstract: The multi-index matching problem (MIMP) generalizes the well known matching problem by going from pairs to d-uplets. We use the cavity method from statistical physics to analyze its properties when the costs of the d-uplets are random. At low temperatures we find for d>2 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.

Recommendations

• Random-link matching problems on random regular graphs
• The random fractional matching problem
• The number of matchings in random graphs
• Bipartite matching and Van der Waerden conjecture
• New estimates on the matching problem

Cites work

• A random tree model associated with random graphs
• Coloring random graphs
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1952026 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 1894374 (Why is no real title available?)
• Letter to the Editor—The Multidimensional Assignment Problem
• Multidimensional assignment formulation of data association problems arising from multitarget and multisensor tracking
• Polymers on disordered trees, spin glasses, and traveling waves.
• Reducibility among combinatorial problems
• Selected topics on assignment problems
• The (2) limit in the random assignment problem
• The cavity method at zero temperature
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(5)

• Surrogate parametric metamodel based on optimal transport
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• The number of matchings in random graphs
• (Dis)assortative partitions on random regular graphs
• Random assignment problems

This page was built for publication: Random multi-index matching problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4968882)