New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
复制标题
通过分层 EDCS 实现完全动态匹配的新权衡
DOI：
10.1137/1.9781611977073.140
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Khanna, Sanjeev.
中科院分区：
文献类型：
--
作者：
Behnezhad, Soheil;Khanna, Sanjeev.
我们研究的最大匹配问题infully dynamicgraphs：一个图正在进行边插入和删除，目标是有效地保持一个大的匹配后，每次边更新。这一问题近年来受到相当大的关注。已知的算法自然地表现出在所保持的匹配质量（即，近似比）和每次更新所需的时间。虽然已经获得了一些有趣的结果，但这种权衡的最佳行为在很大程度上仍然不清楚。我们的主要贡献是设计全动态近似匹配算法的新方法，该算法不仅（本质上）以统一的方式恢复了所有先前已知的通过非常不同的技术实现的权衡，而且还揭示了一些新的权衡。具体来说，我们引入了伯恩斯坦和斯坦（2015）的边度约束子图（EDCS）的推广，我们称之为分层EDCS（HEDCS）。我们还提出了一个随机化算法，有效地保持HEDCS。在最大度为Δ的m-边图中，对于任意整数k ≥ 0，即HEDCS中层次结构的层数，我们的算法取（min{Δ1/（k+ 1），m1/（2k+2）}）最坏情况更新时间，并保持（几乎）α（k）近似匹配，其中我们显示：这些边界恢复了文献中已知的动态匹配的所有先前权衡，直到更新时间的对数因子。对于二分图，α（2）> .612，对于一般图，α（2）> 0.609，注意这些近似值是在（min{Δ1/3，m1/6}）更新时间内得到的，对于二部图，α（3）> 0.563，对于一般图，α（3）> 0.532，注意这些近似值是在（min{Δ1/4，m1/8}）更新时间内得到的。
We study the maximum matching problem infully dynamicgraphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching after each edge update. This problem has received considerable attention in recent years. The known algorithms naturally exhibit a trade-off between the quality of the matching maintained (i.e., the approximation ratio) and the time needed per update. While several interesting results have been obtained, the optimal behavior of this trade-off remains largely unclear. Our main contribution is a new approach to designing fully dynamic approximate matching algorithms that in aunified mannernot only (essentially) recovers all previously known trade-offs that were achieved via very different techniques, but reveals some new ones as well.Specifically, we introduce a generalization of theedge-degree constrained subgraph(EDCS) of Bernstein and Stein (2015) that we call thehierarchical EDCS(HEDCS). We also present a randomized algorithm for efficiently maintaining an HEDCS. In anm-edge graph with maximum degree Δ, for any integerk≥ 0 that is essentially the number of levels of the hierarchy in HEDCS, our algorithm takesÕ(min{Δ1/(k+ 1),m1/(2k+2)}) worst-case update-time and maintains an (almost)α(k)-approximate matching where we show:These bounds recover all previous trade-offs known for dynamic matching in the literature up to logarithmic factors in the update-time.α(2) > .612 for bipartite graphs, andα(2) > .609 for general graphs.Note that these approximations are obtained inÕ(min{Δ1/3,m1/6}) update-time.α(3) > .563 for bipartite graphs, andα(3) > .532 for general graphs.Note that these approximations are obtained inÕ(min{Δ1/4,m1/8}) update-time.
登录
查看更多内容
动态矩阵逆：改进的算法和匹配条件下界
DOI：
10.1109/focs.2019.00036
发表时间：
2019
期刊：
2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Jan van den Brand;Danupon Nanongkai;Thatchaphol Saranurak
通讯作者：
Thatchaphol Saranurak
用于完全动态最大匹配的简单确定性算法
影响因子：
4.4
作者：
Ofer Neiman;Shay Solomon
通讯作者：
Shay Solomon
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.itcs.2022.111
发表时间：
2021
期刊：
ArXiv
影响因子：
--
作者：
M. Roghani;A. Saberi;David Wajc
通讯作者：
David Wajc
动态匹配：将积分算法简化为近似最大分数算法
DOI：
10.4230/lipics.icalp.2018.7
发表时间：
2017
期刊：
ArXiv
影响因子：
--
作者：
Moab Arar;S. Chechik;S. Cohen;Cliff Stein;David Wajc
通讯作者：
David Wajc