mlsanityData to 7 Oct 2026

Fully Dynamic Submodular Maximization over Matroids

arXiv 2305.19918 ↗First posted 31 May 2023cs.DS cs.LG stat.MLcited by 7

Not on the map. Why?

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.

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

Builds on

22 of 41 references.

References · 22

  1. 2020Fairness in Streaming Submodular Maximization: Algorithms and Hardnesscited by 23
  2. 2020Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraintcited by 21
  3. 2017Robust Submodular Maximization: A Non-Uniform Partitioning Approachcited by 15
  4. 2013Submodular Maximization Meets Streaming: Matchings, Matroids, and Morecited by 14
  5. 2017Streaming Robust Submodular Maximization: A Partitioned Thresholding Approachcited by 13
  6. 2018Do Less, Get More: Streaming Submodular Maximization with Subsamplingcited by 12
  7. 2018Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streamscited by 11
  8. 2020Fully Dynamic Algorithm for Constrained Submodular Optimizationcited by 11
  9. 2015Robust Monotone Submodular Function Maximizationcited by 10
  10. 2019Adversarially Robust Submodular Maximization under Knapsack Constraintscited by 9
  11. 2021Streaming Submodular Maximization under Matroid Constraintscited by 9
  12. 2015Streaming Algorithms for Submodular Function Maximizationcited by 7
10 more
  1. 2020The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustnesscited by 7
  2. 2022Deletion Robust Submodular Maximization over Matroidscited by 7
  3. 2021On the Complexity of Dynamic Submodular Maximizationcited by 5
  4. 2023Dynamic Constrained Submodular Optimization with Polylogarithmic Update Timecited by 5
  5. 2016Submodular Optimization over Sliding Windowscited by 4
  6. 2018Towards Nearly-linear Time Algorithms for Submodular Maximization with a Matroid Constraintcited by 4
  7. 2022Coresets remembered and items forgotten: submodular maximization with deletionscited by 4
  8. 2021Cardinality constrained submodular maximization for random streamscited by 2
  9. 2022Deletion Robust Non-Monotone Submodular Maximization over Matroidscited by 2
  10. 2016Submodular Maximization over Sliding Windowscited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 3; 2024: 2; 2025: 0; 2026: 2.

7 papers.

  1. 2023Dynamic Algorithms for Matroid Submodular Maximizationcited by 7
  2. 2023The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformationscited by 4
  3. 2024Consistent Submodular Maximizationcited by 2
  4. 2023Dynamic Non-monotone Submodular Maximizationcited by 1
  5. 2024A Dynamic Algorithm for Weighted Submodular Cover Problemcited by 0
  6. 2026Matroid Algorithms Under Size-Sensitive Independence Oraclescited by 0
  7. 2026A General Framework for Dynamic Consistent Submodular Maximizationcited by 0