# Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

arXiv: https://arxiv.org/abs/1802.06212 · HTML: https://mlsanity.com/paper/1802.06212/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2018.

## Built on by (most cited first, 1 of 1)

- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)

## Abstract (arXiv)

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(varepsilon-1) passes: ----a (1-e-1-varepsilon)-approximation algorithm for the cardinality-constrained problem ---- a (0.5-varepsilon)-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 varepsilon-1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O(nvarepsilon-1 log (varepsilon-1log K) ) time, improving on the algorithm of Badanidiyuru and Vondr'ak that takes O(n varepsilon-1 log (varepsilon-1 K) ) time.