# Deletion Robust Non-Monotone Submodular Maximization over Matroids

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 47 references that are in the map.
- First posted on arXiv 16 Aug 2022.

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

- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [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)
- [Do Less, Get More: Streaming Submodular Maximization with Subsampling](https://mlsanity.com/paper/1802.07098/) (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)
- [Streaming Submodular Maximization under Matroid Constraints](https://mlsanity.com/paper/2107.07183/) (2021)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Submodular Optimization over Sliding Windows](https://mlsanity.com/paper/1610.09984/) (2016)
- [Coresets remembered and items forgotten: submodular maximization with deletions](https://mlsanity.com/paper/2203.01241/) (2022)
- [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, 2 of 2)

- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)

## Abstract (arXiv)

Maximizing a submodular function is a fundamental task in machine learning and 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 (4.597+O(varepsilon))-approximation algorithm with summary size O( frack+dvarepsilon2log frackvarepsilon) that is improved to a (3.582+O(varepsilon))-approximation with O(k + fracdvarepsilon2log frackvarepsilon) summary size when the objective is monotone. In the streaming setting we provide a (9.435 + O(varepsilon))-approximation algorithm with summary size and memory O(k + fracdvarepsilon2log frackvarepsilon); the approximation factor is then improved to (5.582+O(varepsilon)) in the monotone case.