Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

Abstract

We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking $O({\epsilon }^{-1})$ passes: ----a $(1-e^{-1}-\epsilon )$-approximation algorithm for the cardinality-constrained problem ---- a $(0.5-\epsilon )$-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run in $O^{\ast }(n)$ time, using $O^{\ast }(K)$ space, where $n$ is the size of the ground set and $K$ is the size of the knapsack. Here the term $O^{\ast }$ hides a polynomial of $\log K$ and ${\epsilon }^{-1}$. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes $O(n{\epsilon }^{-1}\log ({\epsilon }^{-1}\log K))$ time, improving on the algorithm of Badanidiyuru and Vondrák that takes $O(n{\epsilon }^{-1}\log ({\epsilon }^{-1}K))$ time.