# Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jul 2020.

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

- [A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback](https://mlsanity.com/paper/2301.13326/) (2023)
- [Randomized Greedy Learning for Non-monotone Stochastic Submodular Maximization Under Full-bandit Feedback](https://mlsanity.com/paper/2302.01324/) (2023)
- [Optimal Sampling Gaps for Adaptive Submodular Maximization](https://mlsanity.com/paper/2104.01750/) (2021)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Beyond Pointwise Submodularity: Non-Monotone Adaptive Submodular Maximization subject to Knapsack and k-System Constraints](https://mlsanity.com/paper/2104.04853/) (2021)
- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Fully Dynamic Submodular Maximization over Matroids](https://mlsanity.com/paper/2305.19918/) (2023)
- [Group Equality in Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.03364/) (2022)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Robust Adaptive Submodular Maximization](https://mlsanity.com/paper/2107.11333/) (2021)
- [Partial-Monotone Adaptive Submodular Maximization](https://mlsanity.com/paper/2207.12840/) (2022)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [Partial-Adaptive Submodular Maximization](https://mlsanity.com/paper/2111.00986/) (2021)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [A General Framework for Dynamic Consistent Submodular Maximization](https://mlsanity.com/paper/2606.04946/) (2026)
- [RELS-DQN: A Robust and Efficient Local Search Framework for Combinatorial Optimization](https://mlsanity.com/paper/2304.06048/) (2023)
- [Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies](https://mlsanity.com/paper/2404.01930/) (2024)
- [Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity](https://mlsanity.com/paper/2405.12252/) (2024)
- [Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2409.04415/) (2024)

## Abstract (arXiv)

Constrained submodular maximization problems encompass a wide variety of applications, including personalized recommendation, team formation, and revenue maximization via viral marketing. The massive instances occurring in modern day applications can render existing algorithms prohibitively slow, while frequently, those instances are also inherently stochastic. Focusing on these challenges, we revisit the classic problem of maximizing a (possibly non-monotone) submodular function subject to a knapsack constraint. We present a simple randomized greedy algorithm that achieves a 5.83 approximation and runs in O(n log n) time, i.e., at least a factor n faster than other state-of-the-art algorithms. The robustness of our approach allows us to further transfer it to a stochastic version of the problem. There, we obtain a 9-approximation to the best adaptive policy, which is the first constant approximation for non-monotone objectives. Experimental evaluation of our algorithms showcases their improved performance on real and synthetic data.