2 papers
cond-mat.dis-nn2005
Random multi-index matching problems
O. C. Martin, M. Mezard, O. Rivoire
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 it…
cond-mat.dis-nn2004
A frozen glass phase in the multi-index matching problem
O. C. Martin, M. Mezard, O. Rivoire
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 polynomi…