Carnegie Mellon University
Browse
file.pdf (316.64 kB)

Minimum-cost matching in a random bipartite graph with random costs

Download (316.64 kB)
journal contribution
posted on 2015-06-21, 00:00 authored by Alan FriezeAlan Frieze, Tony Johansson

Let G=Gn,n,p be the random bipartite graph on n+n vertices, where each e∈[n]2 appears as an edge independently with probability p. Suppose that each edge e is given an independent uniform exponential rate one cost. Let C(G) denote the expected length of the minimum cost perfect matching. We show that w.h.p. if d=np≫(logn)2 then E(C(G))=(1+o(1))π2/6p. This generalizes the well-known result for the case G=Kn,n.

History

Date

2015-06-21

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC