Single-pass semi-streaming matching

The question asks whether one pass over a graph, using only semi-streaming space, can beat greedy’s approximation guarantee. It had remained open since the semi-streaming model was introduced by Feigenbaum et al. in 2005.

Known results

• Earlier lower bounds successively ruled out approximation ratios above $2/3$, $(1-1/e) \approx 0.632$, $(1+\ln 2)^{-1} \approx 0.590$, and $(8-2\sqrt{10})/3 \approx 0.558$.
• The preceding blueprint-framework work ruled out every ratio above $(8-2\sqrt{10})/3$ and identified the question as still open.

July 2026 resolution

The paper “Semi-Streaming Matching in a Single Pass II: Greedy is Optimal” proves that no deterministic or randomized single-pass semi-streaming algorithm for maximum bipartite matching achieves any constant approximation ratio strictly greater than $1/2$ with constant probability. Since greedy guarantees $1/2$, it is optimal; the paper also derives the same barrier for online matching with preemption.

Current status (as of August 2026): The problem is resolved: greedy’s $1/2$ approximation is optimal for single-pass semi-streaming maximum bipartite matching, including randomized algorithms.