TY - GEN
T1 - Streaming algorithms for submodular function maximization
AU - Chekuri, Chandra
AU - Gupta, Shalmoli
AU - Quanrud, Kent
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2015.
PY - 2015
Y1 - 2015
N2 - We consider the problem of maximizing a nonnegative submodular set function f: 2N → 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(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.
AB - We consider the problem of maximizing a nonnegative submodular set function f: 2N → 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(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.
UR - http://www.scopus.com/inward/record.url?scp=84950134061&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84950134061&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-47672-7_26
DO - 10.1007/978-3-662-47672-7_26
M3 - Conference contribution
AN - SCOPUS:84950134061
SN - 9783662476710
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 318
EP - 330
BT - Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Proceedings
A2 - Halldorsson, Magnus M.
A2 - Kobayashi, Naoki
A2 - Speckmann, Bettina
A2 - Iwama, Kazuo
PB - Springer
T2 - 42nd International Colloquium on Automata, Languages and Programming, ICALP 2015
Y2 - 6 July 2015 through 10 July 2015
ER -