“In the stochastic weighted matching problem, the goal is to find a large-weight matching of a graph when we are uncertain about the existence of its edges. In particular, each edge e has a known weight we but is realized independently with some probability pe. The algorithm may query an edge to see whether it is realized. We consider the well-studied query commit version of the problem, in which any queried edge that happens to be realized must be included in the solution.”
Find the paper and the full list of authors at SIAM.