Beating the Folklore Algorithm for Dynamic Matching
summary
Deterministic algorithm achieves a deterministic (2−ε)-approx for fully dynamic matching with worst-case update time n^{3/4}. It maintains an epsilon-D kernel sparsifier (D = n^{3/4}) with only one kernel change per graph update, keeps a 3/2+ε bipartite matching between high- and low-degree nodes (via Bernstein–Stein) and runs Gupta–Peng’s bounded-degree routine on the sparsifier; the union of kernel and bipartite matching yields the improved approximation and the stated update bound.
AI-written summary · about