Greedy is optimal for single-pass semi-streaming matching
4 hours ago
- No single-pass semi-streaming algorithm (deterministic or randomized) can achieve better than a half approximation for maximum matching.
- The naive greedy algorithm is proven optimal for semi-streaming matching, resolving a two-decade open question.
- The proof uses a 'blueprint framework' by constructing optimal blueprints to establish the lower bound.
- The result also implies the optimal competitive ratio for online matching with preemption is half, matching the greedy algorithm.