Abstrakt
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 O(n polylog n) memory and a 2-approximation using O(sqrt(nL)) memory.
This is joint work with Cezar-Mihail Alexandru, Christian Konrad, and Kheeran K. Naidu.