Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1\mathrm{/}5-\epsilon$ approximation, falling short of the $1\mathrm{/}4-\epsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1\mathrm{/}4-\epsilon )$-approximation with $O(n{\log }^2(1\mathrm{/}\epsilon )\mathrm{/}{\epsilon }^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1\mathrm{/}2-\epsilon ,O(1\mathrm{/}\epsilon ))$-bicriteria approximation with $O(n\log (1\mathrm{/}\epsilon )\mathrm{/}{\epsilon }^2)$ queries, improving over the previous $O(n^2\mathrm{/}\epsilon )$ query bound.