Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
复制标题
DOI：
10.1145/2764468.2764479
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Ankit Sharma
中科院分区：
文献类型：
--
作者：
Avrim Blum;Nika Haghtalab;Ariel D. Procaccia;Ankit Sharma
随机匹配问题涉及在图中找到最大匹配，该图的边是未知的，但可以通过查询访问。这是随机k-集合包装的一个特例，其中问题是找到集合的最大包装，每个集合都以一定的概率存在。在本文中，我们为这两个问题，分别提供边缘和集合查询算法，可证明实现了一些分数的全知最优解。我们的主要理论结果的随机匹配（即，2-集合包装）问题是设计一个自适应算法，该算法仅查询每个顶点的恒定数量的边，并且对于任意小的ε > 0，实现全知最优解的（1-ε）分数。此外，这种自适应算法执行的查询，只有一个常数轮数。我们用非自适应（即，一轮查询）算法，该算法实现了全知最优的（0.5 - ε）分数。我们还通过设计一个自适应算法将我们的结果扩展到随机k-集包装，该算法实现了全知最优解的（2/k - ε）分数，每个元素仅需O（1）次查询。这种保证接近于确定性k-集填充问题的最佳已知多项式时间近似比3/k+1 -ε [Furer 2013]。我们经验性地探索这些算法的应用（适应）肾脏交换问题，终末期肾功能衰竭患者交换愿意但不相容的供体。我们显示的生成的数据和真实的数据，从第一个169匹配运行的UNOS全国肾脏交换，即使是非常少量的非自适应边缘查询每个顶点的结果在预期的成功匹配的大收益。
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 adaptive algorithm that queries only a constant number of edges per vertex and achieves a (1-ε) fraction of the omniscient optimal solution, for an arbitrarily small ε > 0. Moreover, this adaptive algorithm performs the queries in only a constant number of rounds. We complement this result with a non-adaptive (i.e., one round of queries) algorithm that achieves a (0.5 - ε) fraction of the omniscient optimum. We also extend both our results to stochastic k-set packing by designing an adaptive algorithm that achieves a (2/k - ε) 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 3/k+1 -ε for the deterministic k-set packing problem [Furer 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.