transparent gif

 

Ej inloggad.

Göteborgs universitets publikationer

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

Författare och institution:
Johan Wästlund (Institutionen för matematiska vetenskaper, matematik, Chalmers/GU)
Publicerad i:
Electronic Communications in Probability, 14 s. 261-269
ISSN:
1083-589X
Publikationstyp:
Artikel, refereegranskad vetenskaplig
Publiceringsår:
2009
Språk:
engelska
Fulltextlänk (lokalt arkiv):
Sammanfattning (abstract):
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.
Länk till sammanfattning (abstract):
Ämne (baseras på Högskoleverkets indelning av forskningsämnen):
NATURVETENSKAP ->
Matematik ->
Sannolikhetsteori och statistik ->
Matematisk statistik
Nyckelord:
minimum matching, graph, exponential, matching problems, expected value, mean-field
Postens nummer:
115050
Posten skapad:
2010-02-25 15:37
Posten ändrad:
2016-07-26 11:03

Visa i Endnote-format

Göteborgs universitet • Tel. 031-786 0000
© Göteborgs universitet 2007