Abstract
In the stochastic matching problem, we are given a general (not necessarily bipartite) graph G ( V , E ), where each edge in E is realized with some constant probability p > 0 and the goal is to compute a bounded-degree (bounded by a function depending only on p ) subgraph H of G such that the expected maximum matching size in H is close to the expected maximum matching size in G . The algorithms in this setting are considered non-adaptive as they have to choose the subgraph H without knowing any information about the set of realized edges in G . Originally motivated by an application to kidney exchange , the stochastic matching problem and its variants have received significant attention in recent years.
The state-of-the-art non-adaptive algorithms for stochastic matching achieve an approximation ratio of 1/2-ε for any ε > 0 , naturally raising the question that if 1/2 is the limit of what can be achieved with a non-adaptive algorithm. In this work, we resolve this question by presenting the first algorithm for stochastic matching with an approximation guarantee that is strictly better than 1/2: the algorithm computes a subgraph H of G with the maximum degree O (log(1/ p )/ p such that the ratio of expected size of a maximum matching in realizations of H and G is at least 1/2 + δ 0 for some absolute constant δ 0 > 0 . The degree bound on H achieved by our algorithm is essentially the best possible (up to an O (log(1/p)) factor) for any constant factor approximation algorithm, since an Ω(1/ p ) degree in H is necessary for a vertex to acquire at least one incident edge in a realization.
Our result makes progress towards answering an open problem of Blum et al (EC 2015) regarding the possibility of achieving a (1 - ε)-approximation for the stochastic matching problem using non-adaptive algorithms. From the technical point of view, a key ingredient of our algorithm is a structural result showing that a graph whose expected maximum matching size is OPT always contains a b -matching of size (essentially) b ... OPT, for b = 1/ p .