The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm
复制标题
随机匹配问题：用非自适应算法战胜一半
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yang Li
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;S. Khanna;Yang Li
在随机匹配问题中，我们给定一个一般的（不一定是二分的）图\(G(V,E)\)，其中\(E\)中的每条边以某个大于\(0\)的常数概率\(p\)出现，目标是计算\(G\)的一个有界度（由仅依赖于\(p\)的函数界定）子图\(H\)，使得\(H\)中期望的最大匹配大小接近\(G\)中期望的最大匹配大小。在这种设定下的算法被认为是非自适应的，因为它们必须在不知道\(G\)中已出现边的集合的任何信息的情况下选择子图\(H\)。随机匹配问题最初是由肾脏交换的一个应用所推动的，近年来它及其变体受到了极大的关注。随机匹配的最先进的非自适应算法对于任何\(\varepsilon>0\)都能达到\(1/2 - \varepsilon\)的近似比，这自然引发了一个问题，即\(1/2\)是否是非自适应算法所能达到的极限。在这项工作中，我们通过提出第一个具有严格优于\(1/2\)的近似保证的随机匹配算法来解决这个问题：该算法计算出\(G\)的一个子图\(H\)，其最大度为\(O(\log(1/p)/p)\)，使得在\(H\)和\(G\)的实现中最大匹配的期望大小之比至少为\(1/2+\delta_0\)，其中\(\delta_0>0\)是某个绝对常数。我们的算法所达到的\(H\)的度界对于任何常数因子近似算法来说基本上是最优的（最多相差一个\(O(\log(1/p))\)因子），因为对于一个顶点在一次实现中获得至少一条关联边，\(H\)中的度为\(\Omega(1/p)\)是必要的。我们的结果朝着回答布卢姆等人（EC 2015）关于使用非自适应算法实现随机匹配问题的\((1 - \varepsilon)\)近似的可能性的一个开放问题取得了进展。从技术角度来看，我们算法的一个关键要素是一个结构结果，该结果表明一个期望最大匹配大小为\(OPT\)的图总是包含一个大小为（基本上）\(b\cdot OPT\)的\(b\) - 匹配，其中\(b = 1/p\)。
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.