# Dynamic Algorithms for Matroid Submodular Maximization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 147 references that are in the map.
- First posted on arXiv 1 Jun 2023.

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

- [apricot: Submodular selection for data summarization in Python](https://mlsanity.com/paper/1906.03543/) (2019)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time](https://mlsanity.com/paper/2010.11420/) (2020)
- [Categorical Feature Compression via Submodular Optimization](https://mlsanity.com/paper/1904.13389/) (2019)
- [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 Constrained Submodular Optimization with Polylogarithmic Update Time](https://mlsanity.com/paper/2305.15192/) (2023)
- [Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary](https://mlsanity.com/paper/2004.08432/) (2020)
- [Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time](https://mlsanity.com/paper/2207.07438/) (2022)
- [Dynamic Algorithms for Maximum Matching Size](https://mlsanity.com/paper/2207.07607/) (2022)

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

- [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)
- [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)
- [Multi-Agent Reinforcement Learning with Submodular Reward](https://mlsanity.com/paper/2603.06810/) (2026)
- [Matroid Algorithms Under Size-Sensitive Independence Oracles](https://mlsanity.com/paper/2605.00201/) (2026)

## Abstract (arXiv)

Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial optimization. In this paper, we consider these problems in the dynamic setting, where (1) we have oracle access to a monotone submodular function f: 2V rightarrow ℝ^+ and (2) we are given a sequence S of insertions and deletions of elements of an underlying ground set V. We develop the first fully dynamic (4+ε)-approximation algorithm for the submodular maximization problem under the matroid constraint using an expected worst-case O(klog(k)log3(k/ε)) query complexity where 0 < ε ≤ 1. This resolves an open problem of Chen and Peng (STOC'22) and Lattanzi et al. (NeurIPS'20). As a byproduct, for the submodular maximization under the cardinality constraint k, we propose a parameterized (by the cardinality constraint k) dynamic algorithm that maintains a (2+ε)-approximate solution of the sequence S at any time t using an expected worst-case query complexity O(kε-1log2(k)). This is the first dynamic algorithm for the problem that has a query complexity independent of the size of ground set V.