I will talk about the maximum weighted matching problem in the streaming model. In this model, an algorithm receives edges of a graph one by one. When the stream ends, it should output an approximation of the maximum weighted matching of the input graph using only linear (or subquadratic) memory. First, I will present an algorithm of Paz and Swartzmann, who gave a 2-approximation for this problem. Further, I will talk about how to use this algorithm for design algorithms in sliding window model. In this model, when an edge arrives, the algorithm should output an approximation of the maximum weighted matching in a graph spanned by last L edges, where L is a parameter of the model.
This is a joint work with Cezar-Mihail Alexandru, Christian Konrad, and Kheeran K. Naidu.
