The Stochastic Matching Problem
Authors:
Open Access
- 20 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 99-116
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.Keywords
Funding Information
- National Science Foundation (CCF-1552909 CCF-1617851 and IIS-1447470)
This publication has 21 references indexed in Scilit:
- Paired and Altruistic Kidney Donation in the UKACM Journal of Experimental Algorithmics, 2015
- Finding long chains in kidney exchange using the traveling salesman problemProceedings of the National Academy of Sciences, 2015
- A Stochastic Probing Problem with ApplicationsLecture Notes in Computer Science, 2013
- Stochastic Matching with CommitmentLecture Notes in Computer Science, 2012
- Improved analysis of the greedy algorithm for stochastic matchingInformation Processing Letters, 2011
- When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic MatchingsAlgorithmica, 2011
- Approximating Matches Made in Heaven2009
- On graph problems in a semi-streaming modelTheoretical Computer Science, 2005
- Randomized greedy matching. IIRandom Structures & Algorithms, 1995
- Randomized greedy matchingRandom Structures & Algorithms, 1991