# On the Complexity of Dynamic Submodular Maximization

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 43 references that are in the map.
- First posted on arXiv 5 Nov 2021.

## Builds on (most cited first, 15 of 15)

- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [The Limitations of Optimization from Samples](https://mlsanity.com/paper/1512.06238/) (2015)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [A New Framework for Distributed Submodular Maximization](https://mlsanity.com/paper/1507.03719/) (2015)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model](https://mlsanity.com/paper/1811.03093/) (2018)
- [Comparing Apples and Oranges: Query Tradeoff in Submodular Maximization](https://mlsanity.com/paper/1410.0773/) (2014)
- [Streaming Algorithms for Submodular Function Maximization](https://mlsanity.com/paper/1504.08024/) (2015)
- [The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness](https://mlsanity.com/paper/2003.13459/) (2020)
- [Dynamic Influence Maximization](https://mlsanity.com/paper/2110.12602/) (2021)

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

- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [The Cost of Consistency: Submodular Maximization with Constant Recourse](https://mlsanity.com/paper/2412.02492/) (2024)
- [Dynamic Non-monotone Submodular Maximization](https://mlsanity.com/paper/2311.03685/) (2023)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)
- [A Dynamic Algorithm for Weighted Submodular Cover Problem](https://mlsanity.com/paper/2407.10003/) (2024)

## Abstract (arXiv)

We study dynamic algorithms for the problem of maximizing a monotone submodular function over a stream of n insertions and deletions. We show that any algorithm that maintains a (0.5+ε)-approximate solution under a cardinality constraint, for any constant ε>0, must have an amortized query complexity that is mathitpolynomial in n. Moreover, a linear amortized query complexity is needed in order to maintain a 0.584-approximate solution. This is in sharp contrast with recent dynamic algorithms of [LMNF+20, Mon20] that achieve (0.5-ε)-approximation with a mathsfpolylog(n) amortized query complexity. On the positive side, when the stream is insertion-only, we present efficient algorithms for the problem under a cardinality constraint and under a matroid constraint with approximation guarantee 1-1/e-ε and amortized query complexities smashO(log (k/ε)/ε2) and smashk^tildeO(1/ε2)log n, respectively, where k denotes the cardinality parameter or the rank of the matroid.