Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem

Sepehr Assadi, Sanjeev Khanna, Yang Li

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover (for any $α= o(\sqrt{n…