# Improved Parallel Algorithm for Non-Monotone Submodular Maximization under Knapsack Constraint

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 28 references that are in the map.
- First posted on arXiv 6 Sep 2024.

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

- [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)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Parallel Algorithm for Non-Monotone DR-Submodular Maximization](https://mlsanity.com/paper/1905.13272/) (2019)
- [Unconstrained Submodular Maximization with Constant Adaptive Complexity](https://mlsanity.com/paper/1811.06603/) (2018)
- [Deterministic Approximation for Submodular Maximization over a Matroid in Nearly Linear Time](https://mlsanity.com/paper/2010.11420/) (2020)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Quick Streaming Algorithms for Maximization of Monotone Submodular Functions in Linear Time](https://mlsanity.com/paper/2009.04979/) (2020)
- [Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint](https://mlsanity.com/paper/2009.01947/) (2020)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Improved Deterministic Algorithms for Non-monotone Submodular Maximization](https://mlsanity.com/paper/2208.14388/) (2022)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)

## Abstract (arXiv)

This work proposes an efficient parallel algorithm for non-monotone submodular maximization under a knapsack constraint problem over the ground set of size n. Our algorithm improves the best approximation factor of the existing parallel one from 8+ε to 7+ε with O(log n) adaptive complexity. The key idea of our approach is to create a new alternate threshold algorithmic framework. This strategy alternately constructs two disjoint candidate solutions within a constant number of sequence rounds. Then, the algorithm boosts solution quality without sacrificing the adaptive complexity. Extensive experimental studies on three applications, Revenue Maximization, Image Summarization, and Maximum Weighted Cut, show that our algorithm not only significantly increases solution quality but also requires comparative adaptivity to state-of-the-art algorithms.