Exact solution of the random bipartite matching model

DOI10.1088/0305-4470/33/10/305MaRDI QIDQ4496004zbMATH OpenOpenAlexFDO

Authors Viktor S. Dotsenko

Publication date 13 August 2000

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9911477

zbMATH Keywords

average minimum energyexact solutionParisi conjecturerandom bipartite matching model

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Stochastic methods applied to problems in equilibrium statistical mechanics (82B31)

Abstract: In this paper we present the exact solution for the average minimum energy of the random bipartite matching model with an arbitrary finite number of elements where random paired interactions are described by independent exponential distribution. This solution confirms the Parisi conjecture proposed for this model earlier, as well as the result of the replica solution of this model in the thermodynamic limit.

Recommendations

• Bipartite matching and Van der Waerden conjecture
• Analysis of ground state in random bipartite matching
• The random fractional matching problem
• The Euclidean Matching Problem

Cited in

(8)

• Instability in stable marriage problem: matching unequally numbered men and women
• The planted matching problem: phase transitions and exact results
• Statistical mechanics of a simplified bipartite matching problem: An analytical treatment
• On the maximum of random assignment process
• The (2) limit in the random assignment problem
• The blind passenger and the assignment problem
• On the number of \(k\)-cycles in the assignment problem for random matrices
• Statistical mechanics methods and phase transitions in optimization problems

This page was built for publication: Exact solution of the random bipartite matching model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4496004)