# New Deterministic Approximation Algorithms for Fully Dynamic Matching

arXiv: https://arxiv.org/abs/1604.05765 · HTML: https://mlsanity.com/paper/1604.05765/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Apr 2016.

## Built on by (most cited first, 1 of 1)

- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)

## Abstract (arXiv)

We present two deterministic dynamic algorithms for the maximum matching problem. (1) An algorithm that maintains a (2+ε)-approximate maximum matching in general graphs with O(poly(log n, 1/ε)) update time. (2) An algorithm that maintains an αK approximation of the em value of the maximum matching with O(n2/K) update time in bipartite graphs, for every sufficiently large constant positive integer K. Here, 1≤ αK < 2 is a constant determined by the value of K. Result (1) is the first deterministic algorithm that can maintain an o(log n)-approximate maximum matching with polylogarithmic update time, improving the seminal result of Onak et al. [STOC 2010]. Its approximation guarantee almost matches the guarantee of the best em randomized polylogarithmic update time algorithm [Baswana et al. FOCS 2011]. Result (2) achieves a better-than-two approximation with em arbitrarily small polynomial update time on bipartite graphs. Previously the best update time for this problem was O(m1/4) [Bernstein et al. ICALP 2015], where m is the current number of edges in the graph.