Title: The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm,
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 $\frac{1}{2}-\epsilon$ for any $\epsilon > 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(\frac{\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+\delta_0$ for some absolute constant $\delta_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 $\Omega(\frac{1}{p})$ degree in $H$ is necessary for a vertex to
acquire at least one incident edge in a realization.