  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,
$\mathsf{DLA}$ and $\mathsf{RLA}$. $\mathsf{DLA}$ is a deterministic algorithm
that provides an approximation factor of $6+\epsilon$ while $\mathsf{RLA}$ is a
randomized algorithm with an approximation factor of $4+\epsilon$. Both run in
$O(n \log(1/\epsilon)/\epsilon)$ 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.
