# Streaming Submodular Maximization under Matroid Constraints

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2021.

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

- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)
- [Online and Streaming Algorithms for Constrained k-Submodular Maximization](https://mlsanity.com/paper/2305.16013/) (2023)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)

## Abstract (arXiv)

Recent progress in (semi-)streaming algorithms for monotone submodular function maximization has led to tight results for a simple cardinality constraint. However, current techniques fail to give a similar understanding for natural generalizations, including matroid constraints. This paper aims at closing this gap. For a single matroid of rank k (i.e., any solution has cardinality at most k), our main results are: 1) a single-pass streaming algorithm that uses widetildeO(k) memory and achieves an approximation guarantee of 0.3178, and 2) a multi-pass streaming algorithm that uses widetildeO(k) memory and achieves an approximation guarantee of (1-1/e - varepsilon) by taking a constant (depending on varepsilon) number of passes over the stream. This improves on the previously best approximation guarantees of 1/4 and 1/2 for single-pass and multi-pass streaming algorithms, respectively. In fact, our multi-pass streaming algorithm is tight in that any algorithm with a better guarantee than 1/2 must make several passes through the stream and any algorithm that beats our guarantee of 1-1/e must make linearly many passes (as well as an exponential number of value oracle queries). Moreover, we show how the approach we use for multi-pass streaming can be further strengthened if the elements of the stream arrive in uniformly random order, implying an improved result for p-matchoid constraints.