Skip to yearly menu bar Skip to main content


An Efficient Streaming Algorithm for the Submodular Cover Problem

Ashkan Norouzi-Fard · Abbas Bazzi · Ilija Bogunovic · Marwa El Halabi · Ya-Ping Hsieh · Volkan Cevher

Area 5+6+7+8 #52

Keywords: [ Convex Optimization ] [ Combinatorial Optimization ] [ Clustering ]


We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large-scale graph cover problems.

Live content is unavailable. Log in and register to view live content