# Item

ITEM ACTIONSEXPORT

Released

Paper

#### Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2302.08432.pdf

(Preprint), 756KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Blikstad, J., & Kiss, P. (2023). Incremental (1 - ε)-approximate dynamic matching in O(poly(1/ε)) update time. Retrieved from https://arxiv.org/abs/2302.08432.

Cite as: https://hdl.handle.net/21.11116/0000-000C-A006-8

##### Abstract

In the dynamic approximate maximum bipartite matching problem we are given

bipartite graph $G$ undergoing updates and our goal is to maintain a matching

of $G$ which is large compared the maximum matching size $\mu(G)$. We define a

dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,

\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |

\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -

\beta$).

We present the first deterministic $(1-\epsilon )$-approximate dynamic

matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for

graphs undergoing edge insertions. Previous solutions either required

super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or

exponential in $1/\epsilon $

[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our

implementation is arguably simpler than the mentioned algorithms and its

description is self contained. Moreover, we show that if we allow for additive

$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also

handle vertex deletions, on top of edge insertions. This makes our algorithm

one of the few small update time algorithms for $(1-\epsilon )$-approximate

dynamic matching allowing for updates both increasing and decreasing the

maximum matching size of $G$ in a fully dynamic manner.

bipartite graph $G$ undergoing updates and our goal is to maintain a matching

of $G$ which is large compared the maximum matching size $\mu(G)$. We define a

dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,

\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |

\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -

\beta$).

We present the first deterministic $(1-\epsilon )$-approximate dynamic

matching algorithm with $O(poly(\epsilon ^{-1}))$ amortized update time for

graphs undergoing edge insertions. Previous solutions either required

super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or

exponential in $1/\epsilon $

[Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our

implementation is arguably simpler than the mentioned algorithms and its

description is self contained. Moreover, we show that if we allow for additive

$(1, \epsilon \cdot n)$-approximation our algorithm seamlessly extends to also

handle vertex deletions, on top of edge insertions. This makes our algorithm

one of the few small update time algorithms for $(1-\epsilon )$-approximate

dynamic matching allowing for updates both increasing and decreasing the

maximum matching size of $G$ in a fully dynamic manner.