cs.DS
Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. 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.