Greedy Is Optimal for Single-Pass Semi-Streaming Matching
Sepehr Assadi, Max Jiang, and Mars Xiang report a lower bound proving that no single-pass semi-streaming maximum-matching algorithm beats a 1/2 approximation with constant probability, making the naive greedy algorithm optimal; the evidence is currently an arXiv preprint.
Shay Solomon reports that Sepehr Assadi, Max Jiang, and Mars Xiang have resolved the approximation threshold for single-pass semi-streaming maximum matching, showing that the naive greedy matching algorithm is optimal in this model.
The preprint proves that no deterministic or randomized single-pass semi-streaming algorithm can obtain a constant approximation ratio strictly better than with constant probability; greedy attains . Using the authors' blueprint framework, the result also yields a tight competitive ratio for online matching with preemption. The computational system identified in the sources is the greedy matching algorithm, with no reported AI or automated-prover role; the technical evidence is an arXiv preprint.
Sources: Shay Solomon's announcement
Related Materials: Semi-Streaming Matching in a Single Pass II: Greedy is Optimal