Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time
复制标题
全动态匹配：在 Δϵ 更新时间内击败 2 近似
DOI：
10.1137/1.9781611975994.152
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
V. Mirrokni
中科院分区：
文献类型：
--
作者：
Soheil Behnezhad;Jakub Lacki;V. Mirrokni
在完全动态的图表中，我们知道如何非常快速地维持最大匹配的2个标记，也就是说，在Polyrogarithmic更新时间或更长的时间内。在鲜明的对比和大量研究中，所有已知的算法都保持$ 2- \ omega（1）$近似匹配的速度较慢。尤其是了解这一差距，确定算法的最佳更新时间提供了比2近似匹配更好的匹配是一个主要的开放问题。
在本文中，我们表明，对于任何常数$ \ epsilon> 0 $，有一种随机算法，具有很高的概率可保持$ 2- \ omega（1）$在最差案例中的全动态图中的最大匹配度近似于最大匹配更新时间$ o（\ delta^{\ epsilon}+\ text {polylog} n）$，其中$ \ delta $是最大值 程度。
以前，最快的完全动态匹配算法可提供比2近似更好的近似值的$ O（m^{1/4}）$更新时间[Bernstein and Stein，Soda，2016年]。众所周知，具有更新时间$ O（N^\ epsilon）$的更快算法，但仅用于维持两部分图中匹配的大小（而不是边缘）[Bhattacharya，Henzinger和Nanongkai，STOC 2016]。
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a $2-\Omega(1)$ approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question.
In this paper, we show that for any constant $\epsilon > 0$, there is a randomized algorithm that with high probability maintains a $2-\Omega(1)$ approximate maximum matching of a fully-dynamic general graph in worst-case update time $O(\Delta^{\epsilon}+\text{polylog } n)$, where $\Delta$ is the maximum degree.
Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had $O(m^{1/4})$ update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time $O(n^\epsilon)$ was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].
具有多对数更新时间的全动态最大独立集
DOI：
10.1109/focs.2019.00032
发表时间：
2019
期刊：
{FOCS} 2019
影响因子：
--
作者：
Behnezhad, Soheil;Derakhshan, Mahsa;Hajiaghayi, MohammadTaghi;Stein, Cliff;Sudan, Madhu
通讯作者：
Sudan, Madhu