English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

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

MPS-Authors
/persons/resource/persons285340

Kiss,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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.