CS 269S, Fall 2018: Theory Seminar
Bren Hall, Room 1423, 1pm

November 9, 2018:

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs

Ramtin Afshar

We present a simple single-pass data stream algorithm using $O((\log n)/\varepsilon^2)$ space that returns an $(\alpha + 2)(1 + \varepsilon)$ approximation to the size of the maximum matching in a graph of arboricity $\alpha$.

(Based on a paper by Andrew McGregor and Sofya Vorotnikova from SOSA 2018.)