# Fully Dynamic Submodular Maximization over Matroids

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 41 references that are in the map.
- First posted on arXiv 31 May 2023.

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

- [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)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [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)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (2018)
- [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)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [Adversarially Robust Submodular Maximization under Knapsack Constraints](https://mlsanity.com/paper/1905.02367/) (2019)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [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)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [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)
- [Submodular Optimization over Sliding Windows](https://mlsanity.com/paper/1610.09984/) (2016)
- [Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraint](https://mlsanity.com/paper/1811.07464/) (2018)
- [Coresets remembered and items forgotten: submodular maximization with deletions](https://mlsanity.com/paper/2203.01241/) (2022)
- [Cardinality constrained submodular maximization for random streams](https://mlsanity.com/paper/2111.07217/) (2021)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Submodular Maximization over Sliding Windows](https://mlsanity.com/paper/1611.00129/) (2016)

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

- [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)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (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)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this classic problem in the fully dynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an tildeO(k2) amortized update time (in the number of additions and deletions) and yields a 4-approximate solution, where k is the rank of the matroid.