Minimum Cost Matching in a Random Graph with Random Costs
Minimum Cost Matching in a Random Graph with Random Costs
Let $G_{n,p}$ be the standard Erdös--Rényi--Gilbert random graph and let $G_{n,n,p}$ be the random bipartite graph on $n+n$ vertices, where each $e\in [n]^2$ appears as an edge independently with probability $p$. For a graph $G=(V,E)$, suppose that each edge $e\in E$ is given an independent exponential rate 1 cost $X_e$. …