2017/10/29 by Behnezhad, Soheil, Reyhani, Nima
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1710.10592
We consider the \em stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is \em realized independently with probability p; the realization is initially unknown, however, we are able to \em query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a \em realized matching that is sufficiently close to the maximum matching among all realized edges. This problem has received a considerable attention during the past decade due to its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Our main result is an \em adaptive algorithm that for any arbitrarily small ε> 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate \em non-adaptive algorithm that also queries only O(1) edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi [SODA 2018] achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(wlogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of \em augmenting paths to weighted matchings that may be of independent interest.