Related Experiment Video
Updated: Aug 15, 2026

Determining the Ice-binding Planes of Antifreeze Proteins by Fluorescence-based Ice Plane Affinity
Published on: January 15, 2014
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.
Abstract:
The multi-index matching is an NP-hard combinatorial optimization problem; for two indices it reduces to the well understood bipartite matching problem that belongs to the polynomial complexity class. We use the cavity method to solve the thermodynamics of the multi-index system with random costs. The phase diagram is much richer than for the case of the bipartite matching problem: it shows a finite temperature phase transition to a completely frozen glass phase, similar to what happens in the random energy model. We derive the critical temperature, the ground-state energy density, and properties of the energy landscape and compare the results to numerics based on exact analysis of small systems.
Related Concept Videos
Phase Transitions: Melting and Freezing
Collisions in Multiple Dimensions: Problem Solving
A small car of mass 1,200 kg traveling east at 60 km/h collides at an intersection with a truck of mass 3,000 kg traveling due north at 40 km/h. The two vehicles are locked together. What is the...
Friction: Problem Solving
Initially, a visual representation of the...
Law of Rational Indices
Lagrange Multipliers: Two Constraints
Lagrange Multipliers: Problem Solving

