CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

An easy proof of the zeta(2) limit in the random assignment problem

Johan Wästlund (Institutionen för matematiska vetenskaper, matematik)
Electronic Communications in Probability (1083-589X). Vol. 14 (2009), p. 261-269.
[Artikel, refereegranskad vetenskaplig]

The edges of the complete bipartite graph K-n,K-n are given independent exponentially distributed costs. Let C-n be the minimum total cost of a perfect matching. It was conjectured by M. Mezard and G. Parisi in 1985, and proved by D. Aldous in 2000, that C-n converges in probability to pi(2)/6. We give a short proof of this fact, consisting of a proof of the exact formula 1+1/4+1/9+...+1/n(2) for the expectation of C-n, and a O(1/n)bound on the variance.

Nyckelord: minimum matching, graph, exponential, matching problems, expected value, mean-field

Denna post skapades 2010-02-25. Senast ändrad 2016-07-26.
CPL Pubid: 115050


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)


Matematisk statistik

Chalmers infrastruktur