Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Preprint
Abstract
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic $k$-set packing, where the problem is to find a maximum packing of sets, each of which exists with some probability. In this paper, we provide edge and set query algorithms for these two problems, respectively, that provably achieve some fraction of the omniscient optimal solution. Our main theoretical result for the stochastic matching (i.e., $2$-set packing) problem is the design of an \emph{adaptive} algorithm that queries only a constant number of edges per vertex and achieves a $(1-\epsilon)$ fraction of the omniscient optimal solution, for an arbitrarily small $\epsilon>0$. Moreover, this adaptive algorithm performs the queries in only a constant number of rounds. We complement this result with a \emph{non-adaptive} (i.e., one round of queries) algorithm that achieves a $(0.5 - \epsilon)$ fraction of the omniscient optimum. We also extend both our results to stochastic $k$-set packing by designing an adaptive algorithm that achieves a $(\frac{2}{k} - \epsilon)$ fraction of the omniscient optimal solution, again with only $O(1)$ queries per element. This guarantee is close to the best known polynomial-time approximation ratio of $\frac{3}{k+1} -\epsilon$ for the \emph{deterministic} $k$-set packing problem [Furer and Yu, 2013] We empirically explore the application of (adaptations of) these algorithms to the kidney exchange problem, where patients with end-stage renal failure swap willing but incompatible donors. We show on both generated data and on real data from the first 169 match runs of the UNOS nationwide kidney exchange that even a very small number of non-adaptive edge queries per vertex results in large gains in expected successful matches.
Keywords
All Related Versions
- Version 1, 2014-07-15, ArXiv
- Version 2, 2015-04-29, ArXiv
- Published version: , 325.
This publication has 11 references indexed in Scilit:
- Finding long chains in kidney exchange using the traveling salesman problemProceedings of the National Academy of Sciences, 2015
- Kidney Exchange with Long Chains: An Efficient Pricing Algorithm for Clearing Barter Exchanges with Branch-and-PriceManufacturing & Service Operations Management, 2014
- New insights on integer-programming models for the kidney exchange problemEuropean Journal of Operational Research, 2013
- The Need for (long) Chains in Kidney Exchange2012
- Paired and Altruistic Kidney Donation in the UK: Algorithms and Experimentation2012
- 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
- Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based PreferencesAmerican Economic Review, 2007
- Pairwise kidney exchangeJournal of Economic Theory, 2005
- On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing ProblemsSIAM Journal on Discrete Mathematics, 1989