On the algorithmic side, we give \((1-1/e-\varepsilon )\)  and \((1/e-\varepsilon )\)  approximation for cardinality constrained monotone and non-monotone submodular maximization respectively, both using \(O(k/\varepsilon )\)  memory. The monotone result has an exponential improvement in memory requirements compared to Agrawal et al. [1]} (in terms of the dependence on \(\varepsilon \) ), while the non-monotone result is the first to appear in the random-order streaming model, and improves upon the best known polynomial-time approximations under adversarial orders [2]}. The algorithms are extremely simple to implement, and perform well on real world data (see Section ), even compared to offline greedy algorithms.
