Sliding Window Algorithms for Weighted Matching

I will talk about the maximum weighted matching problem in the streaming sliding window model. In this model, an algorithm receives the edges of a graph one by one. When an edge arrives, the algorithm should output an approximation of the maximum weighted matching in a graph spanned by the last \(L\) edges, where \(L\) is a known parameter. The goal is to design an algorithm with a small approximation factor using as small memory as possible. I will present two algorithms, a \(3\)-approximation using \(\mathcal{O}(n \operatorname{polylog}(n))\) memory and a \(2\)-approximation using \(\mathcal{O}(\sqrt{nL})\) memory.

This is joint work with Cezar-Mihail Alexandru, Christian Konrad, and Kheeran K. Naidu.