论文标题
动态匹配与Polyogarithmic更新时间中的比2近似更好
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
论文作者
论文摘要
我们提出了动态算法，并带有各个元素更新时间，用于估计图形插入和删除的最大匹配度的最大匹配度的大小，近似值的比例严格高于$ 2 $。具体来说，我们获得了$ 1+\ frac {1} {\ sqrt {2}}}+ε\大约1.707+ε$ $近似在两部分图中，而一般图中的$ 1.973+ε$近似值。因此，我们在肯定的肯定中回答了主要的开放问题，首先提出了Onak和Rubinfeld（Stoc'10）的有影响力的工作，并在动态图算法文献中反复提出。我们的随机算法也适用于自适应对手，并保证最差的群体更新时间，均为W.H.P. 我们的算法基于模拟动态设置中的新的两通流媒体匹配算法。我们的主要新想法是以白盒的方式调用Behnezhad（focs'21）的近期跨度时间匹配算法，以有效地模拟我们流媒体算法的第二次通过，同时绕过众所周知的Vertex-Update屏障。
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than $2$. Specifically, we obtain a $1+\frac{1}{\sqrt{2}}+ε\approx 1.707+ε$ approximation in bipartite graphs and a $1.973+ε$ approximation in general graphs. We thus answer in the affirmative the major open question first posed in the influential work of Onak and Rubinfeld (STOC'10) and repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms also work against an adaptive adversary and guarantee worst-case polylog update time, both w.h.p. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.
