# Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 17 references that are in the map.
- First posted on arXiv 11 Sep 2023.

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

- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and k-System Constraints](https://mlsanity.com/paper/2104.04853/) (2021)

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

- [The Power of Second Chance: Personalized Submodular Maximization with Two Candidates](https://mlsanity.com/paper/2409.03545/) (2024)

## Abstract (arXiv)

The objective of a two-stage submodular maximization problem is to reduce the ground set using provided training functions that are submodular, with the aim of ensuring that optimizing new objective functions over the reduced ground set yields results comparable to those obtained over the original ground set. This problem has applications in various domains including data summarization. Existing studies often assume the monotonicity of the objective function, whereas our work pioneers the extension of this research to accommodate non-monotone submodular functions. We have introduced the first constant-factor approximation algorithms for this more general case.