# Non-monotone Sequential Submodular Maximization

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

## Key facts

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

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

- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time](https://mlsanity.com/paper/2008.05004/) (2020)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Adaptive Regularized Submodular Maximization](https://mlsanity.com/paper/2103.00384/) (2021)
- [Sequential Submodular Maximization and Applications to Ranking an Assortment of Products](https://mlsanity.com/paper/2002.09458/) (2020)

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

- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [Learning Submodular Sequencing from Samples](https://mlsanity.com/paper/2409.05265/) (2024)

## Abstract (arXiv)

In this paper, we study a fundamental problem in submodular optimization, which is called sequential submodular maximization. Specifically, we aim to select and rank a group of k items from a ground set V such that the weighted summation of k (possibly non-monotone) submodular functions f1, cdots ,fk: 2V rightarrow ℝ^+ is maximized, here each function fj takes the first j items from this sequence as input. The existing research on sequential submodular maximization has predominantly concentrated on the monotone setting, assuming that the submodular functions are non-decreasing. However, in various real-world scenarios, like diversity-aware recommendation systems, adding items to an existing set might negatively impact the overall utility. In response, this paper pioneers the examination of the aforementioned problem with non-monotone submodular functions and offers effective solutions for both flexible and fixed length constraints, as well as a special case with identical utility functions. The empirical evaluations further validate the effectiveness of our proposed algorithms in the domain of video recommendations. The results of this research have implications in various fields, including recommendation systems and assortment optimization, where the ordering of items significantly impacts the overall value obtained.