Toward Optimal Semi-streaming Algorithm for (1+ε)-approximate Maximum Matching
summary
Deterministic algorithm achieves O(ε^-6) semi-streaming passes for (1+ε)-approximate maximum matching on general graphs, improving prior O(ε^-19). It implements alternating trees and blossom contraction to represent blossoms compactly, caps each tree by freezing tree size at 1/ε^2, and proves overtaking chains have length ≤1/ε so trees cannot explode. Same framework yields the analogous round complexity speed-up in MPC and CONGEST.
AI-written summary · about