Streaming Algorithms for Matchings

In the graph streaming model, an algorithm processes the edges of an input graph one by one while maintaining a memory that is sublinear in the number of edges. In this talk, I will discuss a new augmentation method for matchings in bipartite graphs that yields 2-pass and random order one-pass streaming algorithms that improve on the previously best known algorithms for these models. Based on [Konrad, MFCS 2018].