# Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization in Linear Time

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Aug 2020.

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

- [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)
- [Group Equality in Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.03364/) (2022)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Streaming Adaptive Submodular Maximization](https://mlsanity.com/paper/2208.08021/) (2022)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)
- [Partial-Adaptive Submodular Maximization](https://mlsanity.com/paper/2111.00986/) (2021)
- [Data Summarization beyond Monotonicity: Non-monotone Two-Stage Submodular Maximization](https://mlsanity.com/paper/2309.05183/) (2023)
- [Worst-Case Adaptive Submodular Cover](https://mlsanity.com/paper/2210.13694/) (2022)
- [Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies](https://mlsanity.com/paper/2404.01930/) (2024)
- [The Power of Second Chance: Personalized Submodular Maximization with Two Candidates](https://mlsanity.com/paper/2409.03545/) (2024)

## Abstract (arXiv)

In this paper, we study the non-monotone adaptive submodular maximization problem subject to a cardinality constraint. We first revisit the adaptive random greedy algorithm proposed in citepgotovos2015non, where they show that this algorithm achieves a 1/e approximation ratio if the objective function is adaptive submodular and pointwise submodular. It is not clear whether the same guarantee holds under adaptive submodularity (without resorting to pointwise submodularity) or not. Our first contribution is to show that the adaptive random greedy algorithm achieves a 1/e approximation ratio under adaptive submodularity. One limitation of the adaptive random greedy algorithm is that it requires O(n× k) value oracle queries, where n is the size of the ground set and k is the cardinality constraint. Our second contribution is to develop the first linear-time algorithm for the non-monotone adaptive submodular maximization problem. Our algorithm achieves a 1/e-ε approximation ratio (this bound is improved to 1-1/e-ε for monotone case), using only O(nε-2log ε-1) value oracle queries. Notably, O(nε-2log ε-1) is independent of the cardinality constraint. For the monotone case, we propose a faster algorithm that achieves a 1-1/e-ε approximation ratio in expectation with O(n log frac1ε) value oracle queries. We also generalize our study by considering a partition matroid constraint, and develop a linear-time algorithm for monotone and fully adaptive submodular functions.