A frozen glass phase in the multi-index matching problem

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 numerical studies based on exact analysis of small systems.

References in corpus (7)

• The Bethe lattice spin glass revisited
• Coloring random graphs
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• The glassy phase of Gallager codes
• Statistical mechanics of the vertex-cover problem
• Scaling and Universality in Continuous Length Combinatorial Optimization
• Droplet Phenomenology and Mean Field in a Frustrated and Disordered System

Cited by in corpus (19)

• Clustering of solutions in the random satisfiability problem
• Constraint satisfaction problems with isolated solutions are hard
• Pairs of SAT Assignment in Random Boolean Formulae
• Inference in particle tracking experiments by passing messages between images
• Storage capacity in symmetric binary perceptrons
• Random multi-index matching problems
• The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
• Entropy landscape of solutions in the binary perceptron problem
• Gallager error correcting codes for binary asymmetric channels
• Unsupervised feature learning from finite data by message passing: discontinuous versus continuous phase transition
• On the Atypical Solutions of the Symmetric Binary Perceptron
• (Dis)assortative Partitions on Random Regular Graphs
• Clustering in Hilbert space of a quantum optimization problem
• New Understanding of the Bethe Approximation and the Replica Method
• Statistical mechanics of the maximum-average submatrix problem
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• The statistical mechanics of multi-index matching problems with site disorder
• Planted matching problems on random hypergraphs
• Average case performance of heuristics for multi-dimensional assignment problems