Linear-Time and Deterministic Algorithms for Cardinality-Constrained Non-Monotone Submodular Maximization

For the problem of maximizing a nonnegative, (not necessarily monotone) submodular function with respect to a cardinality constraint, we propose the first deterministic, approximation algorithms with linear time complexity. Our main contribution is a single-pass streaming algorithm that obtains ratio and makes only a constant number of oracle queries per received element. Along the way, we provide a simpler (non-streaming) deterministic, linear-time algorithm with ratio at most 11.657; and a deterministic, linear-time algorithm for the unconstrained maximization problem with competitive ratio 4. Finally, we present a streaming algorithm that, with a constant number of passes, improves the approximation ratio to in linear time. Empirically, the algorithms are validated to use fewer queries than state-of-the-art algorithms.