# Consistent Submodular Maximization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 36 references that are in the map.
- First posted on arXiv 30 May 2024.

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

- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [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)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Consistent k-Median: Simpler, Better and Robust](https://mlsanity.com/paper/2008.06101/) (2020)
- [Consistent k-Clustering for General Metrics](https://mlsanity.com/paper/2011.06888/) (2020)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [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)
- [Fully Dynamic Consistent k-Center Clustering](https://mlsanity.com/paper/2307.13747/) (2023)
- [Efficient and Stable Fully Dynamic Facility Location](https://mlsanity.com/paper/2210.13880/) (2022)
- [Fairness in Streaming Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2305.15118/) (2023)

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

- [The Cost of Consistency: Submodular Maximization with Constant Recourse](https://mlsanity.com/paper/2412.02492/) (2024)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)

## Abstract (arXiv)

Maximizing monotone submodular functions under cardinality constraints is a classic optimization task with several applications in data mining and machine learning. In this paper we study this problem in a dynamic environment with consistency constraints: elements arrive in a streaming fashion and the goal is maintaining a constant approximation to the optimal solution while having a stable solution (i.e., the number of changes between two consecutive solutions is bounded). We provide algorithms in this setting with different trade-offs between consistency and approximation quality. We also complement our theoretical results with an experimental analysis showing the effectiveness of our algorithms in real-world instances.