A Conjecture on random bipartite matching
arXiv:cond-mat/9801176
Abstract
In this note we put forward a conjecture on the average optimal length for bipartite matching with a finite number of elements where the different lengths are independent one from the others and have an exponential distribution.
2 pages, no figures
Cited by in corpus (12)
- The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
- Replica Symmetry and Combinatorial Optimization
- Statistical mechanics methods and phase transitions in optimization problems
- Bivariate Uniqueness and Endogeny for Recursive Distributional Equations : Two Examples
- A proof of a conjecture of Buck, Chan and Robbins on the random assignment problem
- Gaussian Assignment Process
- Computational Complexity for Physicists
- On the expected value of the minimum assignment
- Phase transition in the assignment problem for random matrices
- Bivariate Uniqueness and Endogeny for the Logistic Recursive Distributional Equation
- Belief propagation for minimum weight many-to-one matchings in the random complete graph
- Average case performance of heuristics for multi-dimensional assignment problems