# Enhanced Deterministic Approximation Algorithm for Non-monotone Submodular Maximization under Knapsack Constraint with Linear Query Complexity

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [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)
- [Submodular Maximization in Clean Linear Time](https://mlsanity.com/paper/2006.09327/) (2020)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Linear Query Approximation Algorithms for Non-monotone Submodular Maximization under Knapsack Constraint](https://mlsanity.com/paper/2305.10292/) (2023)
- [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)
- [Approximation Algorithms for Size-Constrained Non-Monotone Submodular Maximization in Deterministic Linear Time](https://mlsanity.com/paper/2104.06873/) (2021)

## Abstract (arXiv)

In this work, we consider the Submodular Maximization under Knapsack (SMK) constraint problem over the ground set of size n. The problem recently attracted a lot of attention due to its applications in various domains of combination optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from 6+ε to 5+ε while keeping the best query complexity of O(n), where ε >0 is a constant parameter. Our technique is based on optimizing the performance of two components: the threshold greedy subroutine and the building of two disjoint sets as candidate solutions. Besides, by carefully analyzing the cost of candidate solutions, we obtain a tighter approximation factor.