Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
Sepehr Assadi, Max Jiang, Mars Xiang
We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the o…
cs.DS2026
Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints
Sepehr Assadi, Max Jiang, Mars Xiang
In the semi-streaming model, we have an -vertex graph whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, us…