The Stochastic Matching Problem With (Very) Few Queries
Authors:
Sepehr Assadi, Sanjeev Khanna, Yang Li.
Abstract:
Motivated by an application in kidney exchange, we study the following stochastic matching problem: we are given
a graph G(V, E) (not necessarily bipartite), where each edge in E is realized with some constant probability p > 0 and the goal is to find a maximum matching
in the realized graph. An algorithm in this setting is allowed to make queries to edges in E in order to determine whether or not they are realized.
We design an adaptive algorithm for this problem that, for any graph G, computes a (1 − ε)-approximate maximum matching in the realized
graph Gp with high probability, while making O(log(1/εp)/εp) queries per vertex, where the edges to query are chosen adaptively in O(log(1/εp)/εp) rounds.
We further present a non-adaptive algorithm that makes O(log(1/εp)/εp) queries per vertex and computes a (0.5 − ε)-approximate
maximum matching in Gp with high probability.
Both our adaptive and non-adaptive algorithms achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) for this problem, while requiring exponentially smaller number of per-vertex queries (and rounds of adaptive queries for the adaptive algorithm). Our results settle an open problem raised by Blum et al. by achieving only a polynomial dependency on both ε and p. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. . This is of particular relevance to the key application of stochastic matching in kidney exchange. We obtain our results via two main techniques, namely matching-covers and vertex sparsification that may be of independent interest.
Both our adaptive and non-adaptive algorithms achieve the same approximation factor as the previous best algorithms of Blum et al. (EC 2015) for this problem, while requiring exponentially smaller number of per-vertex queries (and rounds of adaptive queries for the adaptive algorithm). Our results settle an open problem raised by Blum et al. by achieving only a polynomial dependency on both ε and p. Moreover, the approximation guarantee of our algorithms is instance-wise as opposed to only being competitive in expectation as is the case for Blum et al. . This is of particular relevance to the key application of stochastic matching in kidney exchange. We obtain our results via two main techniques, namely matching-covers and vertex sparsification that may be of independent interest.
Conference version:
[PDF]
Journal version:
[PDF]
BibTex:
[DBLP]