Streaming Algorithms for Submodular Function Maximization

We consider the problem of maximizing a nonnegative submodular set function f:2N rightarrow ℝ^+ subject to a p-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are em non-monotone. We describe deterministic and randomized algorithms that obtain a Omega(frac1p)-approximation using O(k log k)-space, where k is an upper bound on the cardinality of the desired set. The model assumes value oracle access to f and membership oracles for the matroids defining the p-matchoid constraint.