![](/sites/default/files/styles/workshop_banner_sm_1x/public/logo_for_data_structures_and_optimization_for_fast_algorithms_.png.jpg?itok=uePdFHVY)
Abstract
In this talk, we present a simple algorithm for computing (1-eps)-approximation of weighted matching in general (not necessarily bipartite) graphs using O(log(n)/eps) rounds of adaptive sketching. This matches the performance of state-of-the-art algorithms, while being considerably simpler.
The algorithm relies on a "white-box" application of the multiplicative weight update method with a self-contained primal-dual analysis that can be of independent interest.