Towards Tight Bounds for the Streaming Set Cover Problem

Sariel Har-Peled, Piotr Indyk, Sepideh Mahabadi +1

We consider the classic Set Cover problem in the data stream model. For $n$ elements and $m$ sets ($m\ge n$) we give a $O(1/\delta )$-pass algorithm with a strongly sub-linear $\tilde{O…