# Robust Monotone Submodular Function Maximization

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2015.

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

- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Learning for Robust Combinatorial Optimization: Algorithm and Application](https://mlsanity.com/paper/2112.10377/) (2021)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [Robust Sequence Networked Submodular Maximization](https://mlsanity.com/paper/2212.13725/) (2022)

## Abstract (arXiv)

We consider a robust formulation, introduced by Krause et al. (2008), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to τ elements from the chosen set. For the fundamental case of τ=1, we give a deterministic (1-1/e)-1/Theta(m) approximation algorithm, where m is an input parameter and number of queries scale as O(nm+1). In the process, we develop a deterministic (1-1/e)-1/Theta(m) approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (2010), we show a randomized (1-1/e)-ε approximation for constant τ and ε≤ frac1tildeOmega(τ), making O(n1/ε3) queries. Further, for τll √k, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System.