  For the problem of maximizing a nonnegative, (not necessarily monotone)
submodular function with respect to a cardinality constraint, we propose
deterministic algorithms with linear time complexity; these are the first
algorithms to obtain constant approximation ratio with high probability in
linear time. Our first algorithm is a single-pass streaming algorithm that
obtains ratio 9.298 + $\epsilon$ and makes only two queries per received
element. Our second algorithm is a multi-pass streaming algorithm that obtains
ratio 4 + $\epsilon$. Empirically, the algorithms are validated to use fewer
queries than and to obtain comparable objective values to state-of-the-art
algorithms.
