Dynamic Matching - Rounding & Sparsification and New Tools
Explore dynamic matching algorithms and their applications in this lecture from the Simons Institute. Delve into adaptive, polylog update time dynamic matching algorithms yielding (½-ɛ) approximation and (½+δ)-approximate size estimation. Examine the key techniques of dynamic rounding and sparsification via partial rounding. Learn about two new algorithmic primitives robust to adaptive adversaries: fast almost maximal matching (AMM) algorithms and optimal dynamic subset sampling algorithms. Discover the role of AMMs in current polylog time (½+δ)-approximate dynamic matching size estimation algorithms. Gain insights into the latest developments in dynamic graphs and algorithm design from David Wajc of the Technion - Israel Institute of Technology.