# Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 17 May 2023.

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

- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [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)
- ["Bring Your Own Greedy"+Max: Near-Optimal 1/2-Approximations for Submodular Knapsack](https://mlsanity.com/paper/1910.05646/) (2019)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [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)
- [A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint](https://mlsanity.com/paper/1709.09767/) (2017)
- [Improved Deterministic Algorithms for Non-monotone Submodular Maximization](https://mlsanity.com/paper/2208.14388/) (2022)
- [Budget-Feasible Mechanism Design for Non-Monotone Submodular Objectives: Offline and Online](https://mlsanity.com/paper/1905.00848/) (2019)

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

- [Practical Parallel Algorithms for Non-Monotone Submodular Maximization](https://mlsanity.com/paper/2308.10656/) (2023)
- [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)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Fast Approximation Algorithm for Non-Monotone DR-submodular Maximization under Size Constraint](https://mlsanity.com/paper/2511.02254/) (2025)

## Abstract (arXiv)

This work, for the first time, introduces two constant factor approximation algorithms with linear query complexity for non-monotone submodular maximization over a ground set of size n subject to a knapsack constraint, mathsfDLA and mathsfRLA. mathsfDLA is a deterministic algorithm that provides an approximation factor of 6+ε while mathsfRLA is a randomized algorithm with an approximation factor of 4+ε. Both run in O(n log(1/ε)/ε) query complexity. The key idea to obtain a constant approximation ratio with linear query lies in: (1) dividing the ground set into two appropriate subsets to find the near-optimal solution over these subsets with linear queries, and (2) combining a threshold greedy with properties of two disjoint sets or a random selection process to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed solutions with three applications: Revenue Maximization, Image Summarization, and Maximum Weighted Cut, showing that our algorithms not only return comparative results to state-of-the-art algorithms but also require significantly fewer queries.