Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching
Mahsa Derakhshan, Alireza Farhadi · Society for Industrial and Applied Mathematics eBooks · 2023
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. Gamlath, Kale, and Svensson [SODA'19] showed that when the input graph is bipartite, the problem admits a (1 — 1/e)-approximation. In this paper, we give an algorithm that obtains a (1 — 1/e + δ)-approximation for an absolute constant δ > 0.0014, therefore breaking this prevalent bound.