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

2015-06-21T00:00:00Z (GMT) by Alan 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.