Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover

Amit Chakrabarti, Anthony Wirth

Set cover, over a universe of size $n$, may be modelled as a data-streaming problem, where the $m$ sets that comprise the instance are to be read one by one. A semi-streaming algor…