In this talk, we will discuss the problem of finding a maximum matching in the semi-streaming model. In the classical offline model, where we assume that we have enough space to store all vertices and edges of a graph, the problem of computing the maximum matching has been extensively studied. However, in the era of big data, we often face with massive datasets that are too large to fit into the computer's memory. Semi-streaming is one of the models introduced to deal with massive inputs. In this talk, I will present fast algorithms for approximating maximum matching in the semi-streaming model when edges arrive in a random order.

In the first part of the talk, I'll present a single-pass deterministic algorithm that finds a 0.6 approximation of the maximum matching in bipartite graphs. In the second part of the talk, I'll give a reduction from finding a matching in general graphs to finding a matching in bipartite graphs. Using this reduction, I'll show that there exists a single-pass deterministic semi-streaming algorithm that finds a 0.545 approximation of the maximum matching in general graphs.