TY - JOUR

T1 - Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization

AU - Huang, Chien Chung

AU - Kakimura, Naonori

N1 - Funding Information:
The first author was supported by French National Research Agency (ANR), with grant ANR-19-CE48-0016 and ANR-18-CE40-0025-01.The second author was supported by JSPS KAKENHI Grant Numbers JP17K00028, JP18H05291, 20K21834, and 20H05795.
Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

PY - 2021

Y1 - 2021

N2 - We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(ε− 1) passes: (1) a (1 − e− 1 − ε)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 − ε)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O∗(n) time, using O∗(K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O∗ hides a polynomial of logK and ε− 1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O(nε− 1log(ε− 1logK)) time, improving on the algorithm of Badanidiyuru and Vondrák that takes O(nε− 1log(ε− 1K)) time.

AB - We consider maximizing a monotone submodular function under a cardinality constraint or a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access to only a small fraction of the data stored in primary memory. We propose the following streaming algorithms taking O(ε− 1) passes: (1) a (1 − e− 1 − ε)-approximation algorithm for the cardinality-constrained problem, (2) a (0.5 − ε)-approximation algorithm for the knapsack-constrained problem. Both of our algorithms run deterministically in O∗(n) time, using O∗(K) space, where n is the size of the ground set and K is the size of the knapsack. Here the term O∗ hides a polynomial of logK and ε− 1. Our streaming algorithms can also be used as fast approximation algorithms. In particular, for the cardinality-constrained problem, our algorithm takes O(nε− 1log(ε− 1logK)) time, improving on the algorithm of Badanidiyuru and Vondrák that takes O(nε− 1log(ε− 1K)) time.

KW - Approximation algorithms

KW - Streaming algorithms

KW - Submodular function maximization

UR - http://www.scopus.com/inward/record.url?scp=85118668987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85118668987&partnerID=8YFLogxK

U2 - 10.1007/s00224-021-10065-6

DO - 10.1007/s00224-021-10065-6

M3 - Article

AN - SCOPUS:85118668987

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

ER -