Semi-Streaming Set Cover
Yuval Emek, Adi Rosén · ACM Transactions on Algorithms · 2016
This article 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, and the goal is to construct an edge cover F ⊆ E with the objective of minimizing the cardinality (or cost in the weighted case) of F . We further consider a parameterized relaxation of this problem, where, given some 0 ⩽ ϵ 1/√ n O (√ n ), otherwise . In particular, for the traditional set cover problem, we obtain an O (√ n -approximation. This algorithm is proved to be best possible by establishing a family (parameterized by ϵ) of matching lower bounds.