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 0.5 + δ for some absolute constant δ > 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.
Conference version:
[PDF]
Streaming Video:
[YouTube] (presenting at EC'17)
Presentation slides:
[PDF]