Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time
Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time
复制标题
真正次线性更新时间内的动态 (1+ϵ)-近似匹配大小
DOI：
10.1109/focs57990.2023.00095
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Thatchaphol Saranurak
中科院分区：
文献类型：
--
作者：
Sayan Bhattacharya;Peter Kiss;Thatchaphol Saranurak
我们给出了一个完全动态的算法，用$m^{0.5-\Omega_{\epsilon}(1)}$更新时间来保持n点m边图的最大匹配的$(1+\epsilon)$-近似大小。这是对长期存在的$O(N)$更新时间的第一次多项式改进，该时间可以通过定期重新计算获得。因此，我们解决了动态图算法文献(例如，参见[Gupta and Peng FOCS‘13]、[Bernstein and Stein Soda’16]、[Behnezhad and Khanna Soda‘22])的一个主要开放问题的值版本。我们的关键技术部分是关于稠密图上运行时间为次线性的$(1，n)$的第一个次线性算法。所有以前的算法都经历了至少1.499的乘法逼近因子，或者假设图具有非常小的最大度。
We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate size of maximum matching of the graph with n vertices and m edges using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial improvement over the long-standing $O(n)$ update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS’13], [Bernstein and Stein SODA’16], [Behnezhad and Khanna SODA’22]). Our key technical component is the first sublinear algorithm for $(1, \epsilon n)$-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.
登录
查看更多内容
流媒体和动态匹配中的正则引理和障碍
DOI：
10.1145/3564246.3585110
发表时间：
2023
期刊：
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
影响因子：
--
作者：
Assadi, Sepehr;Behnezhad, Soheil;Khanna, Sanjeev;Li, Huan
通讯作者：
Li, Huan
正则化盒单纯形博弈与动态递减二分匹配
DOI：
10.4230/lipics.icalp.2022.77
发表时间：
2022
期刊：
and Programming (ICALP
影响因子：
--
作者：
Jambulapati, Arun;Jin, Yujia;Sidford, Aaron;Tian, Kevin
通讯作者：
Tian, Kevin
DOI：
--
发表时间：
2021
期刊：
--
影响因子：
--
作者：
Bhattacharya S
通讯作者：
Bhattacharya S
DOI：
10.4230/lipics.icalp.2020.30
发表时间：
2020-06
期刊：
--
影响因子：
--
作者：
Yu Chen;Sampath Kannan;S. Khanna
通讯作者：
Yu Chen;Sampath Kannan;S. Khanna
通过局部校正正确学习单调函数
DOI：
10.1109/focs54457.2022.00015
发表时间：
2022
期刊：
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Lange, Jane;Rubinfeld, Ronitt;Vasilyan, Arsen
通讯作者：
Vasilyan, Arsen