Title: A Simple Sparsification Algorithm for Maximum Matching with Applications to Graph Streams
| Speaker: | Sepehr Assadi |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: In this talk, we present a simple algorithm that reduces approximating the maximum weight matching problem in arbitrary graphs to few adaptively chosen instances of the same problem on sparse graphs. In particular, we give an algorithm that, for any eps > 0, computes a (1-eps)-approximate maximum weight matching in arbitrary n-vertex graphs via O(log(n)/eps) call to an algorithm that can solve the same problem on graphs with only O(n/eps) edges.
The algorithm relies on a direct application of the multiplicative weight update method with a self-contained primal-dual analysis. This allows for obtaining a faster convergence rate compared to the applications of generic approaches in this context such as the Plotkin-Shmoys-Tardos framework for packing/covering linear programs.
We will also briefly discuss some applications of this reduction to the design of scalable algorithms on massive graphs, for instance, in the streaming model.