Deterministic Dynamic Matching in Worst-Case Update Time
Deterministic Dynamic Matching in Worst-Case Update Time
复制标题
最坏情况下更新时间的确定性动态匹配
作者：
P. Kiss
We present deterministic algorithms for maintaining a $$(3/2 + epsilon )$$ ( 3 / 2 + ϵ ) and $$(2 + epsilon )$$ ( 2 + ϵ ) -approximate maximum matching in a fully dynamic graph with worst-case update times $${hat{O}}(sqrt{n})$$ O ^ ( n ) and $${ ilde{O}}(1)$$ O ~ ( 1 ) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio $$(2 - delta )$$ ( 2 - δ ) (for any $$delta > 0$$ δ > 0 ) and $$(2 + epsilon )$$ ( 2 + ϵ ) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times $$O(n^{3/4})$$ O ( n 3 / 4 ) and $$O_epsilon (sqrt{n})$$ O ϵ ( n ) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are $$O_epsilon (sqrt{n})$$ O ϵ ( n ) and $${ ilde{O}}(1)$$ O ~ ( 1 ) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving $$(3/2 + epsilon )$$ ( 3 / 2 + ϵ ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a $$(alpha , delta )$$ ( α , δ ) -approximate matching sparsifier if at all times H satisfies that $$mu (H) cdot alpha + delta cdot n ge mu (G)$$ μ ( H ) · α + δ · n ≥ μ ( G ) (define $$(alpha , delta )$$ ( α , δ ) -approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a $$(3/2 + epsilon , delta )$$ ( 3 / 2 + ϵ , δ ) -approximate matching sparsifier. We further show how to reduce the maintenance of an $$alpha $$ α -approximate maximum matching to the maintenance of an $$(alpha , delta )$$ ( α , δ ) -approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of $${hat{O}}(1)$$ O ^ ( 1 ) or $${ ilde{O}}(1)$$ O ~ ( 1 ) and is deterministic or randomized against an adaptive adversary respectively. To achieve $$(2 + epsilon )$$ ( 2 + ϵ ) -approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time.
We present deterministic algorithms for maintaining a $$(3/2 + epsilon )$$ ( 3 / 2 + ϵ ) and $$(2 + epsilon )$$ ( 2 + ϵ ) -approximate maximum matching in a fully dynamic graph with worst-case update times $${hat{O}}(sqrt{n})$$ O ^ ( n ) and $${ ilde{O}}(1)$$ O ~ ( 1 ) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio $$(2 - delta )$$ ( 2 - δ ) (for any $$delta > 0$$ δ > 0 ) and $$(2 + epsilon )$$ ( 2 + ϵ ) were both shown by Roghani et al. (Beating the folklore algorithm for dynamic matching, 2021) with update times $$O(n^{3/4})$$ O ( n 3 / 4 ) and $$O_epsilon (sqrt{n})$$ O ϵ ( n ) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are $$O_epsilon (sqrt{n})$$ O ϵ ( n ) and $${ ilde{O}}(1)$$ O ~ ( 1 ) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving $$(3/2 + epsilon )$$ ( 3 / 2 + ϵ ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 2015). Say that H is a $$(alpha , delta )$$ ( α , δ ) -approximate matching sparsifier if at all times H satisfies that $$mu (H) cdot alpha + delta cdot n ge mu (G)$$ μ ( H ) · α + δ · n ≥ μ ( G ) (define $$(alpha , delta )$$ ( α , δ ) -approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a $$(3/2 + epsilon , delta )$$ ( 3 / 2 + ϵ , δ ) -approximate matching sparsifier. We further show how to reduce the maintenance of an $$alpha $$ α -approximate maximum matching to the maintenance of an $$(alpha , delta )$$ ( α , δ ) -approximate maximum matching building based on an observation of Assadi et al. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of $${hat{O}}(1)$$ O ^ ( 1 ) or $${ ilde{O}}(1)$$ O ~ ( 1 ) and is deterministic or randomized against an adaptive adversary respectively. To achieve $$(2 + epsilon )$$ ( 2 + ϵ ) -approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time.
登录
查看更多内容
随机顺序流匹配击败三分之二
DOI：
10.4230/lipics.icalp.2021.19
发表时间：
2021
期刊：
Scotland (Virtual Conference
影响因子：
--
作者：
Assadi, Sepehr;Behnezhad, Soheil
通讯作者：
Behnezhad, Soheil
DOI：
10.4230/lipics.icalp.2022.20
发表时间：
2020-04
期刊：
ArXiv
影响因子：
--
作者：
A. Bernstein;Jan van den Brand;M. Gutenberg;Danupon Nanongkai;Thatchaphol Saranurak;Aaron Sidford;He Sun
通讯作者：
A. Bernstein;Jan van den Brand;M. Gutenberg;Danupon Nanongkai;Thatchaphol Saranurak;Aaron Sidford;He Sun
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
核心集满足 EDCS：海量图上的匹配和顶点覆盖算法
DOI：
--
发表时间：
2019
期刊：
SODA 2019
影响因子：
--
作者：
Assadi, S.
Batenai
通讯作者：
Assadi, S.
Batenai