We consider the problem of maximizing a nonnegative sub-modular set function f : 2~N → R~+ 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 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 / and membership oracles for the matroids defining the p-matchoid constraint.
展开▼
