The variance and higher moments in the random assignment problem
2005 (English)Report (Other academic)
We obtain exact formulas for all moments of the cost Cn of the inimum assignment in the complete bipartite graph Kn,n with independent exp(1) edge costs. In particular we prove that as n tends to infinity, the variance of Cn is c/n+O(1/n2), where c = 4ζ(2)-4ζ(3), or approximately 1.7715.
Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press , 2005. , 19 p.
Linköping Studies in Mathematics, ISSN 1652-4454 (online), 0348-2960 (print) ; 8
IdentifiersURN: urn:nbn:se:liu:diva-62953OAI: oai:DiVA.org:liu-62953DiVA: diva2:375263