Streaming Algorithms for Connectivity Augmentation
summary
Presents single‑pass streaming algorithms and matching lower bounds: link‑arrival k‑CAP gets a 2+ε approximation using O(n/ε · log n) space and shows any <2 approximation needs Ω(n^2) bits; edge‑arrival gives an O(t) approximation using O(k n + n^{1+1/t}) space. Key tools are even‑odd bucketing and contracting connected components into supernodes, which lets weighted spanners be built in one pass with ~n^{1+1/t} edges (replace log W by log n). Cactus→cycle reduction yields a 2‑approx for link streams and extends to SNDP with t·log k approx and matching lower bounds.
AI-written summary · about