Surveys:
Online Matching: A Brief Survey
Zhiyi Huang, Zhihao Gavin Tang and David Wajc
Survey
Summary: A brief survey of the online matching literature, with an emphasis on developments since the influential 2013 survey of Mehta on the topic.
(Appearing in SIGecom Exchanges 2024)
Dynamic Matching Algorithms and Dynamic Matching Sparsifiers
David Wajc
Talk
Summary: In this talk I give a brief overview of the dynamic matching literature, and emphasize one key ingredient in many of the known dynamic matching algorithms: dynamically maintaining matching sparsifiers.
(Part of the STOC'22 Workshop on Dynamic Algorithms)
Dynamic Matching: Rounding & Sparsification (and New Tools)
David Wajc
Talk
Summary: In this talk I give an overview of key tools for polylog update time dynamic matching: rounding of fractional matchings, and sparsification. (Bonus@end: overview of a few new adaptive data structures of broader interest.)
(Part of the Simons Workshop on Dynamic Graphs and Algorithms Design)