# Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2020.

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

- [Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel](https://mlsanity.com/paper/2111.07917/) (2021)
- [Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraint](https://mlsanity.com/paper/2405.13994/) (2024)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Scalable Distributed Algorithms for Size-Constrained Submodular Maximization in the MapReduce and Adaptive Complexity Models](https://mlsanity.com/paper/2206.09563/) (2022)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)
- [Fast Stochastic Greedy Algorithm for k-Submodular Cover Problem](https://mlsanity.com/paper/2511.00869/) (2025)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

We consider the problem of monotone, submodular maximization over a ground set of size n subject to cardinality constraint k. For this problem, we introduce the first deterministic algorithms with linear time complexity; these algorithms are streaming algorithms. Our single-pass algorithm obtains a constant ratio in lceil n / c rceil + c oracle queries, for any c ≥ 1. In addition, we propose a deterministic, multi-pass streaming algorithm with a constant number of passes that achieves nearly the optimal ratio with linear query and time complexities. We prove a lower bound that implies no constant-factor approximation exists using o(n) queries, even if queries to infeasible sets are allowed. An empirical analysis demonstrates that our algorithms require fewer queries (often substantially less than n) yet still achieve better objective value than the current state-of-the-art algorithms, including single-pass, multi-pass, and non-streaming algorithms.