Title: Streaming algorithms for submodular function maximization

Authors: C. Chekuri, S. Gupta, and K. Quanrud


We consider the problem of maximizing a nonnegative submodular set function $f:2^{ℝ+}$ 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 $Ω(1/p)$-approximation using O(klogk)-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.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale