Greedy is optimal for single-pass semi-streaming matching

Researchers proved that no single-pass semi-streaming algorithm can achieve better than a 50% approximation for the maximum matching problem, establishing that the simple greedy algorithm is optimal—a question open for over two decades. The proof uses an "optimal blueprint construction" within a previously introduced framework, and the results also settle the optimal competitive ratio for online matching with preemption at one-half.