Stochastic matching with few queries: (1-ε) approximation

Suppose that we are given an arbitrary graph G = (V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G. The maximum degree of Q can depend on p, but not on the size of G. This problem has been subject to extensive studies over the years and the approximation factor has been improved from 0.5 [10, 4] to 0.5001 [5] to 0.6568 [7] and eventually to 2/3 [3] . In this work, we analyze a natural sampling-based algorithm and show that it can obtain all the way up to (1 -ε) approximation, for any constant ε > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier [4, 5] towards achieving (1-ε) approximation based on existence of dense Ruzsa-Szemerédi graphs.