Almost Optimal Stochastic Weighted Matching with Few Queries
Almost Optimal Stochastic Weighted Matching with Few Queries
复制标题
几乎最优的随机加权匹配与很少的查询
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Reyhani
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;N. Reyhani
我们考虑了随机匹配的问题。但是，我们能够查询边缘以确定它们是否已实现。边缘。在Chen等人的最初论文中，随机匹配问题在过去的十年中得到了考虑。 。我们的主要结果是一种自适应算法，对于任何任意的小ε> 0，可以通过查询每个顶点的o（1）边缘来找到预期中的（1-ε）app。 /2-ε） - 在我们工作之前使用$ o（1）$边缘的非自动算法Maehara和Yamaguchi的最先进的自适应（分别不自适应）算法实现A（1-ε） - approximation（分别（1/2-ε） - approximation），通过查询至o（w livugnogn） ）每个顶点的边缘w表示最大整数边缘权重。仅查询一个常数每个顶点的边缘数量。
We consider the stochastic matching problem. An edge-weighted general (i.e., not necessarily bipartite) graph G(V, E) is given in the input, where each edge in E is realized independently with probability p ; the realization is initially unknown, however, we are able to query the edges to determine whether they are realized. The goal is to query only a small number of edges to find a realized matching that is sufficiently close to the maximum matching among all realized edges. The stochastic matching problem has received a considerable attention during the past decade after the initial paper of Chen et al. [ICALP'09] because of its numerous real-world applications in kidney-exchange, matchmaking services, online labor markets, and advertisements. Most relevant to our work are the recent papers of Blum et al. [EC'15], Assadi et al. [EC'16, EC'17] and Maehara and Yamaguchi~[SODA'18] that consider the same model of stochastic matching. Our main result is an adaptive algorithm that for any arbitrarily small ε > 0, finds a (1-ε)-approximation in expectation, by querying only O(1) edges per vertex. We further show that our approach leads to a (1/2-ε)-approximate non-adaptive algorithm that also uses $O(1)$ edges per vertex. Prior to our work, no nontrivial approximation was known for weighted graphs using a constant per-vertex budget. The state-of-the-art adaptive (resp. non-adaptive) algorithm of Maehara and Yamaguchi achieves a (1-ε)-approximation (resp. (1/2-ε)-approximation) by querying up to O(w łogn) edges per vertex where w denotes the maximum integer edge-weight. Our result is a substantial improvement over this bound and has an appealing message: No matter what the structure of the input graph is, one can get arbitrarily close to the optimum solution by querying only a constant number of edges per vertex. To obtain our results, we introduce novel properties of a generalization of augmenting paths to weighted matchings that may be of independent interest.