Researchers have proven that no single-pass semi-streaming algorithm, whether deterministic or randomized, can achieve a better-than-half approximation for the maximum matching problem. This finding confirms the optimality of the naive greedy algorithm, resolving a significant open question in graph streaming literature that has persisted for over two decades.

The proof utilizes the "blueprint framework," previously developed by the authors. This framework simplifies the task of establishing lower bounds for semi-streaming matching by focusing on the construction of specific combinatorial objects known as blueprints. The paper introduces an optimal construction of these blueprints, which, when applied within the framework, directly leads to the derived lower bound for semi-streaming matching.

Furthermore, the results extend to the realm of online matching with preemption, demonstrating that the optimal competitive ratio is half. This also aligns with the performance of the naive greedy algorithm, thereby settling another long-standing open question in the field.