“We study maximum matchings in fully dynamic graphs, … graphs that undergo both edge insertions and deletions. Our focus is on algorithms that estimate the size of maximum matching after each update while spending a small time. … We show that for any fixed ɛ > 0, a (2 — √2— ɛ) approximation can be maintained in poly(log n) time per update even in general graphs. Our techniques also lead to the same approximation for general graphs in two passes of the semi-streaming setting, removing a similar gap.”

Find the paper and authors list in the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms proceedings.