Beating the Folklore Algorithm for Dynamic Matching
Beating the Folklore Algorithm for Dynamic Matching
复制标题
打破动态匹配的民间传说算法
DOI：
10.4230/lipics.itcs.2022.111
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
David Wajc
中科院分区：
文献类型：
--
作者：
M. Roghani;A. Saberi;David Wajc
动态图中的最大匹配问题受到边缘更新（插入和删除）在过去的几年中受到了很大的关注，获得了大量的近似/时间权衡，改进后的民俗算法，它保持了最大（因此2 $近似）匹配在$O（n）$最坏情况下的更新时间在$n$-节点图。我们提出了第一个确定性算法，它优于民俗算法的近似比和最坏情况下的更新时间。具体地说，我们给出了一个$（2-\Omega（1））$-近似算法，在$n$-节点，$m$-边图中，最坏情况下的更新时间为O（m^{3/8}）=O（n^{3/4}）$.对于足够小的常数$\n>0$，没有已知的最坏情况更新时间为O（n^{0.99}）$的确定性$（2+\n）$近似算法。我们的第二个结果是第一个确定性的$（2+\n）$-近似加权匹配算法，最坏情况下的更新时间为O_\n（1）\cdot O（\sqrt[4]{m}）= O_\n（1）\cdot O（\sqrt{n}）。我们的主要技术贡献是三方面的：首先，我们的特点紧的情况下，\n {内核}，这是充分研究的匹配稀疏基本的$（2+\n）$-近似动态匹配文献。这种特征以及多个想法（新旧）构成了我们突破2美元近似障碍的结果。我们的第二个技术贡献是动态匹配算法的第一个例子，由于改进了其他动态匹配算法的资源，该算法的运行时间得到了改进。最后，我们将展示如何使用动态二分匹配算法的黑盒子子程序的动态匹配一般的图形，而不会产生自然的$\frac{3}{2}$因子的近似比，这种方法自然产生。
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence $2$-approximate) matching in $O(n)$ worst-case update time in $n$-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of {\em both} approximation ratio and worst-case update time. Specifically, we give a $(2-\Omega(1))$-approximate algorithm with $O(m^{3/8})=O(n^{3/4})$ worst-case update time in $n$-node, $m$-edge graphs. For sufficiently small constant $\epsilon>0$, no deterministic $(2+\epsilon)$-approximate algorithm with worst-case update time $O(n^{0.99})$ was known. Our second result is the first deterministic $(2+\epsilon)$-approximate weighted matching algorithm with $O_\epsilon(1)\cdot O(\sqrt[4]{m}) = O_\epsilon(1)\cdot O(\sqrt{n})$ worst-case update time. Our main technical contributions are threefold: first, we characterize the tight cases for \emph{kernels}, which are the well-studied matching sparsifiers underlying much of the $(2+\epsilon)$-approximate dynamic matching literature. This characterization, together with multiple ideas -- old and new -- underlies our result for breaking the approximation barrier of $2$. Our second technical contribution is the first example of a dynamic matching algorithm whose running time is improved due to improving the \emph{recourse} of other dynamic matching algorithms. Finally, we show how to use dynamic bipartite matching algorithms as black-box subroutines for dynamic matching in general graphs without incurring the natural $\frac{3}{2}$ factor in the approximation ratio which such approaches naturally incur.
登录
查看更多内容
通过 Nibble 方法的在线边缘着色算法
DOI：
10.1137/1.9781611976465.168
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Sayan Bhattacharya;F. Grandoni;David Wajc
通讯作者：
David Wajc
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Bhattacharya S
通讯作者：
Bhattacharya S
DOI：
10.1145/3406325.3451113
发表时间：
2021
期刊：
Symposium on Theory of Computing
影响因子：
--
作者：
Bernstein, Aaron;Dudeja, Aditi;Langley, Zachary
通讯作者：
Langley, Zachary
具有多对数更新时间的全动态最大独立集
DOI：
10.1109/focs.2019.00032
发表时间：
2019
期刊：
{FOCS} 2019
影响因子：
--
作者：
Behnezhad, Soheil;Derakhshan, Mahsa;Hajiaghayi, MohammadTaghi;Stein, Cliff;Sudan, Madhu
通讯作者：
Sudan, Madhu