“In this paper, we study the weighted stochastic matching problem. Let G=(V,E) be a given edge-weighted graph and let its realization G be a random subgraph of G that includes each edge e∈E independently with a known probability pe. The goal in this problem is to pick a sparse subgraph Q of G without prior knowledge of G’s realization, such that the maximum weight matching among the realized edges of Q (i.e. the subgraph Q∩) in expectation approximates the maximum weight matching of the entire realization G.”

Find the paper and full list of authors at ArXiv.