# The Cost of Consistency: Submodular Maximization with Constant Recourse

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 24 references that are in the map.
- First posted on arXiv 3 Dec 2024.

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

- [Submodular Maximization Meets Streaming: Matchings, Matroids, and More](https://mlsanity.com/paper/1309.2038/) (2013)
- [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)
- [Deterministic Algorithms for Submodular Maximization Problems](https://mlsanity.com/paper/1508.02157/) (2015)
- [The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness](https://mlsanity.com/paper/2003.13459/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [Dynamic Algorithms for Matroid Submodular Maximization](https://mlsanity.com/paper/2306.00959/) (2023)
- [Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint](https://mlsanity.com/paper/2408.03583/) (2024)
- [On the Complexity of Dynamic Submodular Maximization](https://mlsanity.com/paper/2111.03198/) (2021)
- [Fully Dynamic Consistent k-Center Clustering](https://mlsanity.com/paper/2307.13747/) (2023)
- [Online Discrepancy with Recourse for Vectors and Graphs](https://mlsanity.com/paper/2111.06308/) (2021)
- [Fully Dynamic k-Clustering with Fast Update Time and Small Recourse](https://mlsanity.com/paper/2408.01325/) (2024)
- [Fully-Dynamic Submodular Cover with Bounded Recourse](https://mlsanity.com/paper/2009.00800/) (2020)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)

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

- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)
- [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)

In this work, we study online submodular maximization, and how the requirement of maintaining a stable solution impacts the approximation. In particular, we seek bounds on the best-possible approximation ratio that is attainable when the algorithm is allowed to make at most a constant number of updates per step. We show a tight information-theoretic bound of tfrac23 for general monotone submodular functions, and an improved (also tight) bound of tfrac34 for coverage functions. Since both these bounds are attained by non poly-time algorithms, we also give a poly-time randomized algorithm that achieves a 0.51-approximation. Combined with an information-theoretic hardness of tfrac12 for deterministic algorithms from prior work, our work thus shows a separation between deterministic and randomized algorithms, both information theoretically and for poly-time algorithms.