Greedy is optimal for single-pass semi-streaming matching
semi-streamingmatchingalgorithmgraphgreedy
Author: MarcoDewey
Date: 7/21/2026
Article Summary:
The paper proves that no single-pass semi-streaming algorithm can achieve a better-than-half approximation to the maximum matching problem, implying the optimality of the naive greedy algorithm.