# Partial-Monotone Adaptive Submodular Maximization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 22 references that are in the map.
- First posted on arXiv 26 Jul 2022.

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

- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [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)
- [Using Partial Monotonicity in Submodular Maximization](https://mlsanity.com/paper/2202.03051/) (2022)
- [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)
- [Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio](https://mlsanity.com/paper/1904.10748/) (2019)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Price of Dependence: Stochastic Submodular Maximization with Dependent Items](https://mlsanity.com/paper/1905.09719/) (2019)
- [Partial-Adaptive Submodular Maximization](https://mlsanity.com/paper/2111.00986/) (2021)

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

- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Worst-Case Adaptive Submodular Cover](https://mlsanity.com/paper/2210.13694/) (2022)

## Abstract (arXiv)

Many sequential decision making problems, including pool-based active learning and adaptive viral marketing, can be formulated as an adaptive submodular maximization problem. Most of existing studies on adaptive submodular optimization focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, citegolovin2011adaptive developed a greedy policy that achieves a (1-1/e) approximation ratio subject to a cardinality constraint. If the utility function is non-monotone and adaptive submodular, citetang2021beyond showed that a random greedy policy achieves a 1/e approximation ratio subject to a cardinality constraint. In this work, we aim to generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio m∈[0,1] to measure the degree of monotonicity of a function. Our main result is to show that a random greedy policy achieves an approximation ratio of m(1-1/e)+(1-m)(1/e) if the utility function is m-adaptive monotone and adaptive submodular. Notably this result recovers the aforementioned (1-1/e) and 1/e approximation ratios when m = 0 and m = 1, respectively. We further extend our results to consider a knapsack constraint. We show that a sampling-based policy achieves an approximation ratio of (m+1)/10 if the utility function is m-adaptive monotone and adaptive submodular. One important implication of our results is that even for a non-monotone utility function, we still can achieve an approximation ratio close to (1-1/e) if this function is ``close'' to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.