A Simple -Approximation Adaptive Sketching Algorithm for Maximum Weighted Matching

Explore a 47-minute lecture by Sepehr Assadi from the University of Waterloo and Rutgers University, presented at the Simons Institute. Delve into a simple algorithm for computing (1-eps)-approximation of weighted matching in general graphs using O(log(n)/eps) rounds of adaptive sketching. Learn how this approach matches state-of-the-art algorithms while offering greater simplicity. Discover the algorithm's reliance on a "white-box" application of the multiplicative weight update method, featuring a self-contained primal-dual analysis that may be of broader interest. Gain insights into advanced concepts in sketching and algorithm design for maximum weighted matching problems.

A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching