Streaming Weighted Matchings: Optimal Meets Greedy

Understand

We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph $G(V,E)$ are revealed in a streaming fashion.

• We analyze a variant of the previously best-known $(4+\epsilon)$-approximation algorithm due to Crouch and Stubbs (APPROX, 2014), and prove their conjecture that it achieves a tight approximation factor of $3.5+\epsilon$.
• The algorithm splits the stream into substreams on which it runs a greedy maximum matching algorithm.
• At the end of the stream, the selected edges are given as input to an optimal maximum weighted matching algorithm.