# Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 54 references that are in the map.
- First posted on arXiv 16 Feb 2021.

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

- [Adaptivity in Adaptive Submodularity](https://mlsanity.com/paper/1911.03620/) (2019)
- [Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint](https://mlsanity.com/paper/2007.05014/) (2020)
- [Scalable Greedy Feature Selection via Weak Submodularity](https://mlsanity.com/paper/1703.02723/) (2017)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [The FAST Algorithm for Submodular Maximization](https://mlsanity.com/paper/1907.06173/) (2019)
- [Fully Dynamic Algorithm for Constrained Submodular Optimization](https://mlsanity.com/paper/2006.04704/) (2020)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [Non-monotone Submodular Maximization in Exponentially Fewer Iterations](https://mlsanity.com/paper/1807.11462/) (2018)
- [Submodular Maximization with Matroid and Packing Constraints in Parallel](https://mlsanity.com/paper/1808.09987/) (2018)
- [Parallelizing greedy for submodular set function maximization in matroids and beyond](https://mlsanity.com/paper/1811.12568/) (2018)
- [Parallel Algorithm for Non-Monotone DR-Submodular Maximization](https://mlsanity.com/paper/1905.13272/) (2019)
- [Submodular Function Maximization in Parallel via the Multilinear Relaxation](https://mlsanity.com/paper/1807.08678/) (2018)
- [An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model](https://mlsanity.com/paper/1811.03093/) (2018)
- [Unconstrained Submodular Maximization with Constant Adaptive Complexity](https://mlsanity.com/paper/1811.06603/) (2018)
- [Submodular Maximization Through Barrier Functions](https://mlsanity.com/paper/2002.03523/) (2020)
- [A Parallel Double Greedy Algorithm for Submodular Maximization](https://mlsanity.com/paper/1812.01591/) (2018)

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

- [Deletion Robust Submodular Maximization over Matroids](https://mlsanity.com/paper/2201.13128/) (2022)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [Deletion Robust Non-Monotone Submodular Maximization over Matroids](https://mlsanity.com/paper/2208.07582/) (2022)
- [Consistent Submodular Maximization](https://mlsanity.com/paper/2405.19977/) (2024)
- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (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)

Submodular maximization is a classic algorithmic problem with multiple applications in data mining and machine learning; there, the growing need to deal with massive instances motivates the design of algorithms balancing the quality of the solution with applicability. For the latter, an important measure is the adaptive complexity, which captures the number of sequential rounds of parallel computation needed by an algorithm to terminate. In this work we obtain the first constant factor approximation algorithm for non-monotone submodular maximization subject to a knapsack constraint with near-optimal O(log n) adaptive complexity. Low adaptivity by itself, however, is not enough: a crucial feature to account for is represented by the total number of function evaluations (or value queries). Our algorithm asks tildeO(n2) value queries, but can be modified to run with only tildeO(n) instead, while retaining a low adaptive complexity of O(log2n). Besides the above improvement in adaptivity, this is also the first combinatorial approach with sublinear adaptive complexity for the problem and yields algorithms comparable to the state-of-the-art even for the special cases of cardinality constraints or monotone objectives.