Random multi-index matching problems

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.

22 pages, 16 figures

References in corpus (11)

• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Glass models on Bethe lattices
• The glassy phase of Gallager codes
• A frozen glass phase in the multi-index matching problem
• Comparing Mean Field and Euclidean Matching Problems
• On the finite size corrections to some random matching problems
• Neighborhood preferences in random matching problems

Cited by in corpus (11)

• The number of matchings in random graphs
• Behavior of Ising Spin Glasses in a Magnetic Field
• Constraint satisfaction problems with isolated solutions are hard
• The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
• Random-field p-spin glass model on regular random graphs
• One-loop diagrams in the Random Euclidean Matching Problem
• (Dis)assortative Partitions on Random Regular Graphs
• Distribution of partition function zeros of the $\pm J$ model on the Bethe lattice
• Code optimization, frozen glassy phase and improved decoding algorithms for low-density parity-check codes
• Phase transition in the bipartite z-matching
• Planted matching problems on random hypergraphs