Sieve-Streaming and Sieve-Streaming++ for Single-Pass Monotone Submodular Maximization

Sieve-Streaming and Sieve-Streaming++ for Single-Pass Monotone Submodular Maximization are single-pass streaming data summarization algorithms introduced by Badanidiyuru, Mirzasoleiman, Karbasi, and Krause (2014) and tightened to optimal O(k / varepsilon) memory by Kazemi, Mitrovic, Zadimoghaddam, Lattanzi, and Karbasi (2019) for maximizing a non-negative monotone submodular function f : 2^V -> R_{>=0} subject to a cardinality constraint |S| <= k over a stream V. Because the offline optimum OPT = max_{|S|<=k} f(S) is unknown a priori, Sieve-Streaming tracks the running maximum singleton value Delta = max_{e seen} f({e}), maintains geometric threshold guesses tau in {(1 + varepsilon)^i} covering the active OPT range, and inserts an incoming stream element e into candidate set S_tau whenever |S_tau| < k and its marginal gain satisfies f({e} | S_tau) >= tau (achieving the tight single-pass streaming approximation ratio 1/2 - varepsilon in O(k log(k) / varepsilon) memory). Sieve-Streaming++ (Algorithm 1, Theorem 1) observes that the best current sieve value LB = max_tau f(S_tau) provides a monotonically improving lower bound on OPT, allowing the algorithm to dynamically discard all sieves with tau < tau_min = max(LB, Delta) / (2k) and bounding the cardinality of every surviving sieve with tau >= LB / (2k) by |S_tau| <= min(k, LB / tau), which forms a geometric series summing to the asymptotically optimal memory footprint O(k / varepsilon) while preserving O(log(k) / varepsilon) queries per element and the tight (1/2 - varepsilon) approximation.