Ignorance is almost bliss: near-optimal stochastic matching with few queries

DOI10.1287/OPRE.2019.1856MaRDI QIDQ5130481zbMATH OpenOpenAlexWikidataFDO

Authors John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, Ankit Sharma, Avrim Blum

Publication date 4 November 2020

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.4094, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.704.3790

zbMATH Keywords

kidney exchangematching with queriesstochastic matching

Mathematics Subject Classification ID

Stochastic programming (90C15) Combinatorial optimization (90C27)

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 $(frac2k-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 $frac3k+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.

Recommendations

• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• Stochastic Matching with Few Queries: New Algorithms and Tools
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Approximating Matches Made in Heaven
• Improved approximation algorithms for stochastic matching

Cites work

• A dynamic model of barter exchange
• A stochastic probing problem with applications
• Approximating Matches Made in Heaven
• Approximating the k-set packing problem by local improvements
• Approximating the stochastic Knapsack problem: the benefit of adaptivity
• Dynamic kidney exchange
• Free riding and participation in large scale, multi-hospital kidney exchange
• scientific article; zbMATH DE number 7053373 (Why is no real title available?)
• Improved analysis of the greedy algorithm for stochastic matching
• Kidney Exchange
• New insights on integer-programming models for the kidney exchange problem
• 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 Problems
• Pairwise kidney exchange
• Random graphs.
• Stochastic matching with commitment
• When LP is the cure for your matching woes: improved bounds for stochastic matchings

Cited in

(8)

• Output sensitive fault tolerant maximum matching
• An adversarial model for scheduling with testing
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Set selection under explorable stochastic uncertainty via covering techniques
• A recourse policy to improve number of successful transplants in uncertain kidney exchange programs
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Maximum-expectation matching under recourse
• On the complexity of knapsack under explorable uncertainty: hardness and algorithms

This page was built for publication: Ignorance is almost bliss: near-optimal stochastic matching with few queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5130481)