Semi-Streaming Set Cover

Yuval Emek, Adi Rosen

This paper studies the set cover problem under the semi-streaming model. The underlying set system is formalized in terms of a hypergraph $G=(V,E)$ whose edges arrive one-by-one…