Stochastic matching with few queries: (1-ε) approximation
Stochastic matching with few queries: (1-ε) approximation
复制标题
少量查询的随机匹配：(1-ε) 近似
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
M. Hajiaghayi
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Mahsa Derakhshan;M. Hajiaghayi
假设我们得到了一个任意的图G =（V，E），并且知道E中的每个边缘将在某些概率p中独立实现。 Q中已实现的边缘的预期，包括一个匹配，大约与G的最大匹配大约大大。Q的最大程度可以取决于P，但不取决于G的大小。经过多年来的大量研究，近似因素已从0.5逐渐提高到2/3，这是一项已知的障碍。对于任何常数є> 0。我们分析的键和可能的独立兴趣组成部分是一种算法，该算法是在随机图上构造匹配的算法，在其他一些重要属性中，可以保证每个顶点与每个顶点都独立于匹配。足够远的顶点使我们绕过基于密集的Ruzsa-szemerédi图的先前已知的障碍。
Suppose that we are given an arbitrary graph G=(V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G. The maximum degree of Q can depend on p, but not on the size of G. This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.
DOI：
10.1137/1.9781611974782.155
发表时间：
2017
期刊：
SIAM: ACM-SIAM Symposium on Discrete Algorithms (SODA17
影响因子：
--
作者：
Blum, Avrim;Caragiannis, Ioannis;Haghtalab, Nika;Procaccia, Ariel D.;Procaccia, Eviatar B.;Vaish, Rohit
通讯作者：
Vaish, Rohit
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai