# Robust Submodular Maximization: A Non-Uniform Partitioning Approach

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jun 2017.

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

- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [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)
- [Fair Submodular Cover](https://mlsanity.com/paper/2407.04804/) (2024)
- [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)
- [Instance Specific Approximations for Submodular Maximization](https://mlsanity.com/paper/2102.11911/) (2021)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Localized Distributional Robustness in Submodular Multi-Task Subset Selection](https://mlsanity.com/paper/2404.03759/) (2024)
- [Parallel Quasi-concave set optimization: A new frontier that scales without needing submodularity](https://mlsanity.com/paper/2108.08758/) (2021)
- [Robust Sequence Networked Submodular Maximization](https://mlsanity.com/paper/2212.13725/) (2022)
- [Robust Information Selection for Hypothesis Testing with Misclassification Penalties](https://mlsanity.com/paper/2502.14738/) (2025)
- [Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits](https://mlsanity.com/paper/2606.08977/) (2026)

## Abstract (arXiv)

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint k, with the added twist that a number of items τ from the returned set may be removed. We focus on the worst-case setting considered in (Orlin et al., 2016), in which a constant-factor approximation guarantee was given for τ = o(√k). In this paper, we solve a key open problem raised therein, presenting a new Partitioned Robust (PRo) submodular maximization algorithm that achieves the same guarantee for more general τ = o(k). Our algorithm constructs partitions consisting of buckets with exponentially increasing sizes, and applies standard submodular optimization subroutines on the buckets in order to construct the robust solution. We numerically demonstrate the performance of PRo in data summarization and influence maximization, demonstrating gains over both the greedy algorithm and the algorithm of (Orlin et al., 2016).