  We study the problem of maximizing a non-monotone submodular function subject
to a cardinality constraint in the streaming model. Our main contribution is a
single-pass (semi-)streaming algorithm that uses roughly $O(k / \varepsilon^2)$
memory, where $k$ is the size constraint. At the end of the stream, our
algorithm post-processes its data structure using any offline algorithm for
submodular maximization, and obtains a solution whose approximation guarantee
is $\frac{\alpha}{1+\alpha}-\varepsilon$, where $\alpha$ is the approximation
of the offline algorithm. If we use an exact (exponential time) post-processing
algorithm, this leads to $\frac{1}{2}-\varepsilon$ approximation (which is
nearly optimal). If we post-process with the algorithm of Buchbinder and
Feldman (Math of OR 2019), that achieves the state-of-the-art offline
approximation guarantee of $\alpha=0.385$, we obtain $0.2779$-approximation in
polynomial time, improving over the previously best polynomial-time
approximation of $0.1715$ due to Feldman et al. (NeurIPS 2018). It is also
worth mentioning that our algorithm is combinatorial and deterministic, which
is rare for an algorithm for non-monotone submodular maximization, and enjoys a
fast update time of $O(\frac{\log k + \log (1/\alpha)}{\varepsilon^2})$ per
element.
