Streaming Algorithms for Cardinality-Constrained Maximization of Non-Monotone Submodular Functions in Linear Time

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.