A framework for dynamic matching in weighted graphs
A framework for dynamic matching in weighted graphs
复制标题
加权图中动态匹配的框架
DOI：
10.1145/3406325.3451113
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Langley, Zachary
中科院分区：
文献类型：
--
作者：
Bernstein, Aaron;Dudeja, Aditi;Langley, Zachary
我们引入了一个用于计算近似最大权重匹配的新框架。我们的主要关注点是完全动态的设置，其中用于计算加权和未加权匹配的最著名算法的保证之间存在很大差距。事实上，几乎所有当前的加权匹配算法都可以减少未加权问题的近似率损失两倍。相比之下，在其他次线性模型（例如分布式和流式模型）中，最近的工作在很大程度上缩小了这种加权/未加权差距。对于二分图，我们几乎完全通过一般减少来解决差距，即将 α 近似未加权匹配的算法转换为 (1−)α 近似加权匹配的算法，同时仅将常数 的更新时间增加 O(logn) 因子。我们还表明，我们的框架导致了非二部图的显着改进，尽管不是以通用归约的形式。特别地，我们给出了两种加权非二分匹配算法： 1．一种随机（拉斯维加斯）完全动态算法，在最坏情况更新时间 O(polylogn) 中保持 (1/2−) 近似最大权重匹配，以高概率对抗自适应对手。我们的界限本质上与 Wajc [STOC 2020] 的未加权算法的界限相同。 2. 确定性全动态算法，在摊销更新时间 O(m1/4) 内保持 (2/3−) 近似最大权重匹配。我们的边界本质上与 Bernstein 和 Stein [SODA 2016] 的未加权算法的边界相同。我们框架的一个关键特征是它使用现有算法作为黑盒进行未加权匹配。因此，我们的框架简单且通用。此外，我们的框架可以轻松地转换为其他模型，并且我们使用它来为流和通信复杂性模型中的加权匹配问题得出新结果。
We introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted matchings. Indeed, almost all current weighted matching algorithms that reduce to the unweighted problem lose a factor of two in the approximation ratio. In contrast, in other sublinear models such as the distributed and streaming models, recent work has largely closed this weighted/unweighted gap.For bipartite graphs, we almost completely settle the gap with a general reduction that convertsanyalgorithm for α-approximate unweighted matching to an algorithm for (1−)α-approximate weighted matching, while only increasing the update time by anO(logn) factor for constant . We also show that our framework leads to significant improvements for non-bipartite graphs, though not in the form of a universal reduction. In particular, we give two algorithms for weighted non-bipartite matching:1. A randomized (Las Vegas) fully dynamic algorithm that maintains a (1/2−)-approximate maximum weight matching in worst-case update timeO(polylogn) with high probability against an adaptive adversary. Our bounds are essentially the same as those of the unweighted algorithm of Wajc [STOC 2020]. 2. A deterministic fully dynamic algorithm that maintains a (2/3−)-approximate maximum weight matching in amortized update timeO(m1/4). Our bounds are essentially the same as those of the unweighted algorithm of Bernstein and Stein [SODA 2016].A key feature of our framework is that it uses existing algorithms for unweighted matching as black-boxes. As a result, our framework is simple and versatile. Moreover, our framework easily translates to other models, and we use it to derive new results for the weighted matching problem in streaming and communication complexity models.
登录
查看更多内容
O (log n) 更新时间内的完全动态最大匹配
DOI：
--
发表时间：
2011
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Surender Baswana;Manoj Gupta;Sandeep Sen
通讯作者：
Sandeep Sen
动态匹配：将积分算法简化为近似最大分数算法
DOI：
10.4230/lipics.icalp.2018.7
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Moab Arar;S. Chechik;S. Cohen;Cliff Stein;David Wajc
通讯作者：
David Wajc
全动态匹配：在 Δϵ 更新时间内击败 2 近似
DOI：
10.1137/1.9781611975994.152
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
Soheil Behnezhad;Jakub Lacki;V. Mirrokni
通讯作者：
V. Mirrokni
DOI：
10.1137/s0097539799361208
发表时间：
2000
期刊：
ArXiv
影响因子：
--
作者：
M. Kao;T. Lam;W. Sung;H. Ting
通讯作者：
H. Ting
动态 Spanner 和动态最大匹配的去摊方法
DOI：
10.1145/3469833
发表时间：
2018
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
A. Bernstein;S. Forster;Monika Henzinger
通讯作者：
Monika Henzinger