# Deletion Robust Submodular Maximization over Matroids

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [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)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [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)
- [Distributionally Robust Submodular Maximization](https://mlsanity.com/paper/1802.05249/) (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)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [A New Framework for Distributed Submodular Maximization](https://mlsanity.com/paper/1507.03719/) (2015)
- [Adversarially Robust Submodular Maximization under Knapsack Constraints](https://mlsanity.com/paper/1905.02367/) (2019)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Submodular Optimization over Sliding Windows](https://mlsanity.com/paper/1610.09984/) (2016)
- [Deletion-Robust Submodular Maximization at Scale](https://mlsanity.com/paper/1711.07112/) (2017)
- [Submodular Optimization Over Streams with Inhomogeneous Decays](https://mlsanity.com/paper/1811.05652/) (2018)

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

- [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)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [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 a monotone submodular function is a fundamental task in machine learning. In this paper, we study the deletion robust version of the problem under the classic matroids constraint. Here the goal is to extract a small size summary of the dataset that contains a high value independent set even after an adversary deleted some elements. We present constant-factor approximation algorithms, whose space complexity depends on the rank k of the matroid and the number d of deleted elements. In the centralized setting we present a (3.582+O(varepsilon))-approximation algorithm with summary size O(k + fracd log kvarepsilon2). In the streaming setting we provide a (5.582+O(varepsilon))-approximation algorithm with summary size and memory O(k + fracd log kvarepsilon2). We complement our theoretical results with an in-depth experimental analysis showing the effectiveness of our algorithms on real-world datasets.