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

View PDF HTML (experimental) Abstract:We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering an outstanding open question in the graph streaming literature since the introduction of the model over two decades ago. Our proof follows the "blueprint framework" introduced previously by the authors, which reduced proving lower bounds for semi-streaming matching to constructing certain combinatorial objects called blueprints. We present an optimal construction of blueprints that when used in this framework implies our semi-streaming matching lower bound. Our results also imply that the optimal competitive ratio of online matching with preemption is half, again matching the naive greedy algorithm, settling this open question as well.

Comments: 23 pages, 3 figures. Version 2: Fixed typos and minor language issues throughout

Subjects: Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC) Cite as: arXiv:2607.14656 [cs.DS]   (or arXiv:2607.14656v2 [cs.DS] for this version)   https://doi.org/10.48550/arXiv.2607.14656 arXiv-issued DOI via DataCite Submission history From: Sepehr Assadi [view email] [v1] Thu, 16 Jul 2026 07:22:45 UTC (39 KB) [v2] Mon, 20 Jul 2026 02:47:00 UTC (39 KB)