Stochastic Matching with Few Queries: New Algorithms and Tools
Stochastic Matching with Few Queries: New Algorithms and Tools
复制标题
少量查询的随机匹配：新算法和工具
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
N. Reyhani
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Alireza Farhadi;M. Hajiaghayi;N. Reyhani
我们在加权和未加权图上考虑以下随机匹配问题：图$ g（v，e）$以及参数$ p \ in（0，1）$在输入中给出。 $ g $的每个边缘都可以独立实现概率$ p $。目标是选择$ g $的学位（仅取决于$ p $）$ h $的$ h $，以使$ h $的最大实现匹配的预期大小/重量接近$ g $。
由于其各种应用，这种随机匹配模型在近年来引起了极大的关注。最基本的开放性问题是对于此类算法而言，可以实现的最佳近似因素，在文献中被称为非自适应算法。先前的工作已经确定了打破（接近）的半轴氧化是加权图和未加权图的障碍。我们的主要结果如下：
- 我们分析了一种简单干净的算法，并表明对于未加权的图，它可以通过查询$ o（\ frac {\ log（\ frac {\ log）（\ frac {\ log（\ frac { 1/p）} {p}）$每个顶点。这比Assadi等人的最先进的$ 0.5001 $大约算法改善了。 [EC'17]。
- 我们表明，同一算法通过查询$ o（\ frac {\ log（1/p）} {p}）$ edges $ edge $ o（\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {\ frac {p}）$ edges $ edges $ edge of $ evers $ edge y。这是第一个打破加权图$ 0.5 $近似屏障的算法。它还改善了Yamaguchi和Maehara [Soda'18]以及Behnezhad和Reyhani [EC'18]的最先进的vertex查询。
我们的算法与先前的作品根本不同，但非常简单和自然。为了进行分析，我们介绍了许多构建重分匹配的程序。我们将新算法和分析工具视为本文的主要贡献。
We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph $G(V, E)$ along with a parameter $p \in (0, 1)$ is given in the input. Each edge of $G$ is realized independently with probability $p$. The goal is to select a degree bounded (dependent only on $p$) subgraph $H$ of $G$ such that the expected size/weight of maximum realized matching of $H$ is close to that of $G$.
This model of stochastic matching has attracted significant attention over the recent years due to its various applications. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows:
-- We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) $4\sqrt{2}-5$ ($\approx 0.6568$) approximation by querying $O(\frac{\log (1/p)}{p})$ edges per vertex. This improves over the state-of-the-art $0.5001$ approximate algorithm of Assadi et al. [EC'17].
-- We show that the same algorithm achieves a $0.501$ approximation for weighted graphs by querying $O(\frac{\log (1/p)}{p})$ edges per vertex. This is the first algorithm to break $0.5$ approximation barrier for weighted graphs. It also improves the per-vertex queries of the state-of-the-art by Yamaguchi and Maehara [SODA'18] and Behnezhad and Reyhani [EC'18].
Our algorithms are fundamentally different from prior works, yet are very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.