Concentration of the cost of a random matching problem
(English)Manuscript (preprint) (Other academic)
Let Mn be the minimum cost of a perfect matching on a complete graph on n vertices whose edges are assigned independent exponential costs. It follows from work of D. Aldous that Mn converges in probability to π2/12. This was earlier conjectured by M. Mézard and G. Parisi. We establish the more precise result that E | Mn – π2/12| = O(n-1/2).
IdentifiersURN: urn:nbn:se:liu:diva-51715OAI: oai:DiVA.org:liu-51715DiVA: diva2:277088