# A General Framework for Dynamic Consistent Submodular Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 33 references that are in the map.
- First posted on arXiv 3 Jun 2026.

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

- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Online Submodular Maximization with Preemption](https://mlsanity.com/paper/1501.05801/) (2015)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness](https://mlsanity.com/paper/2003.13459/) (2020)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [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)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Dynamic Constrained Submodular Optimization with Polylogarithmic Update Time](https://mlsanity.com/paper/2305.15192/) (2023)
- [Coresets remembered and items forgotten: submodular maximization with deletions](https://mlsanity.com/paper/2203.01241/) (2022)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [The Cost of Consistency: Submodular Maximization with Constant Recourse](https://mlsanity.com/paper/2412.02492/) (2024)
- [Chasing Submodular Objectives, and Submodular Maximization via Cutting Planes](https://mlsanity.com/paper/2511.13605/) (2025)

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

- [A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over 2-√2 Entails Exponential Queries or Linear Recourse](https://mlsanity.com/paper/2609.09986/) (2026)

## Abstract (arXiv)

Consistency is an important property in dynamic submodular maximization and entails maintaining a near-optimal solution at all times, making only a small number of adjustments to the solution in each step. Prior work has explored this question for the insertion-only case, where the algorithm faces a stream of n insertions, and has established lower and upper bounds for the cardinality-constrained version of the problem. We consider this question in the fully dynamic setting, where the stream of operations may contain both insertions and deletions. We develop a general framework for designing algorithms for this setting, and instantiate it to obtain the first constant-factor approximations with sublinear consistency. For cardinality constraints, we propose a frac 12 - O(varepsilon) approximation that is Oleft(frac1varepsilon2right) consistent. For rank-k matroid constraints, we construct a frac 14 - O(varepsilon) approximation to the dynamic optimum that is Oleft(fraclog kvarepsilon2right) consistent.