Minimum-cost matching in a random bipartite graph with random costs
<p>Let G=G<sub>n,n,p</sub> be the random bipartite graph on n+n vertices, where each e∈[n]<sup>2</sup> 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)<sup>2</sup> then E(C(G))=(1+o(1))π<sup>2</sup>/<sub>6p</sub>. This generalizes the well-known result for the case G=K<sub>n,n</sub>.</p>