Related Experiment Videos
Frozen glass phase in the multi-index matching problem
O C Martin1, M Mézard, O Rivoire
1Laboratoire de Physique Théorique et Modèles Statistiques, bâtiment 100, Universitá Paris-Sud, F-91405 Orsay, France.
Physical Review Letters
|December 17, 2004
Summary
We solved the complex multi-index matching problem using the cavity method. This reveals a rich phase diagram with a novel glass phase transition at finite temperatures.
Area of Science:
- Statistical physics
- Combinatorial optimization
Background:
- Multi-index matching is an NP-hard problem.
- Bipartite matching (two indices) is computationally tractable.
Purpose of the Study:
- To apply the cavity method to multi-index matching with random costs.
- To analyze the thermodynamic properties and phase diagram of this system.
Main Methods:
- Cavity method for solving statistical mechanics of disordered systems.
- Derivation of critical temperature and ground-state energy density.
Main Results:
- A richer phase diagram than bipartite matching.
- Discovery of a finite-temperature phase transition to a glassy state.
- Analytical results for critical temperature, ground-state energy, and energy landscape properties.
Conclusions:
- The cavity method provides insights into complex combinatorial problems.
- Multi-index matching exhibits complex thermodynamic behavior, including glassy phases.
- Analytical findings are consistent with numerical simulations.