Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity

In this work, we consider the Submodular Maximization under Knapsack ( \(\textsf{SMK}\) $\mathsf{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 combinatorial optimization, artificial intelligence, and machine learning. We improve the approximation factor of the fastest deterministic algorithm from \(6+\epsilon \) $6+ϵ$ to \(5+\epsilon \) $5+ϵ$ while keeping the best query complexity of O(n), where \(\epsilon >0\) $ϵ>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.