July 21, 2026
Greed, for once, is good
Greedy is optimal for single-pass semi-streaming matching
After 20 years of brainy debate, the basic grab-it-first method wins and the comments are losing it
TLDR: Researchers say that in a fast, memory-limited matching problem, the simple greedy approach cannot be beaten, ending a 20-year open debate. The community’s reaction was a mix of awe, laughter, and mild despair that the “obvious” method won after all.
The big shocker here is almost insultingly simple: after more than two decades of smart people trying to beat the obvious approach, researchers say the plain old "take the next good pair you see" method is as good as it gets in this one-pass, low-memory setting. In normal-person terms, if you have to make decisions on the fly and you can’t keep the whole problem in your head, fancy tricks won’t save you. That alone sent comment sections into a full identity crisis.
A lot of the loudest reactions were some version of, “So the dumb method was secretly the genius method all along?” That sparked two camps instantly. Team Vindication was popping champagne for greedy algorithms everywhere, joking that “my lazy coding habits are now mathematically certified.” Team Existential Dread, meanwhile, read it as a brutal reminder that sometimes whole fields spend years proving you can’t outsmart a very basic idea. Several commenters compared it to discovering your grandpa’s “just eyeball it” strategy was actually optimal.
The humor practically wrote itself. Memes about “task failed successfully” and “local guy accidentally achieves theoretical optimum” flew around, along with jokes that computer science had just handed a lifetime achievement award to the bare minimum. But beneath the laughs was real admiration: even skeptical readers admitted that finally closing a long-running open question is a huge deal, especially when it also settles a related online decision-making problem too.
Key Points
- •The article proves that no deterministic or randomized single-pass semi-streaming algorithm can achieve better than a 1/2 approximation for maximum matching.
- •This establishes the naive greedy algorithm as optimal in the single-pass semi-streaming setting.
- •The result answers a longstanding open question in graph streaming literature dating back more than two decades.
- •The proof uses the previously introduced blueprint framework and an optimal construction of combinatorial objects called blueprints.
- •The findings also imply that online matching with preemption has an optimal competitive ratio of 1/2, matching naive greedy and settling another open question.