Entropy Regularization and Faster Decremental Matching in General Graphs

Jiale Chen, Aaron Sidford, Ta-Wei Tu

We provide an algorithm that maintains, against an adaptive adversary, a $(1-\epsilon )$-approximate maximum matching in $n$-node $m$-edge general (not necessarily bipartite) und…