Greedy is Optimal: Solving the Two-Decade-Old Graph Streaming Mystery

Greedy is optimal for single-pass semi-streaming matching

We finally prove that no single-pass semi-streaming algorithm can beat the simple greedy approach for maximum matching. This result settles a major open question in graph streaming literature that has persisted for over twenty years. By constructing optimal combinatorial blueprints, we demonstrate that the naive greedy algorithm is indeed the best possible solution, also confirming the limits of online matching with preemption.

"We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem."