Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
This work studies non-monotone SMK and focuses on deterministic algorithms with linear query complexity and obtains a deterministic submodular maximization approximation with bicriteria approximation with O(n\log(1/\varepsilon)/\varepsilon)/\varepsilon^2) queries, improving over the previous $O(n^2/\varepsilon)$ query...