Approximation limits for one-pass semi-streaming bipartite matching

What maximum-bipartite-matching approximation is possible in one-pass semi-streaming with O(n polylog n) memory and constant success probability? The proposed barrier is one half even for randomized algorithms, matching greedy.

Why it matters and what counts as progress

Why it matters: It asks whether more sophisticated single-pass methods can improve on the simplest approximation within the same memory budget.

What counts as progress: A lower bound matching one-half approximation for randomized single-pass algorithms, or an algorithm beating it under changed pass or memory assumptions.

How the problem developed

2012 · Algorithm [1]
Christian Konrad, Frédéric Magniez and Claire Mathieu Recorded the 1/2 greedy baseline and open arbitrary-order question, while obtaining a small improvement under uniformly random edge arrival.
16 Jul 2026 · Partial result [2]
Sepehr Assadi, Max Jiang and Mars Xiang Introduced a blueprint framework for lower bounds and narrowed the possible one-pass approximation beyond earlier bounds.
16 Jul 2026 · Hardness result [3]
Sepehr Assadi, Max Jiang and Mars Xiang Proved no deterministic or randomized single-pass semi-streaming algorithm can beat 1/2, matching greedy for maximum matching.

AI contribution

Semi-Streaming Matching in a Single Pass II: Greedy is Optimal

Sepehr Assadi, Max Jiang, Mars Xiang

Assadi, Jiang and Xiang construct optimal blueprints showing that no deterministic or randomized single-pass semi-streaming algorithm using O(n polylog n) memory and constant success probability can guarantee better than a one-half approximation for maximum bipartite matching. Greedy attains one half.

AI involvementAI-centered

ImportanceMajor

Technical verificationPartial

Human understandingFull