http://swrc.ontoware.org/ontology#TechnicalReport
Multi-Pass Streaming Algorithms for Monotone Submodular Function Maximization
en
CNRS, Ecole Normale Superieure
Department of Mathematics, Keio University
Chien-Chung Huang
Naonori Kakimura
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 log K 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ε-1 log (ε-1 log K) ) time, improving on the algorithm of Badanidiyuru and Vondrak that takes O (nε-1 log (ε-1K) ) time.
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 log K 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ε-1 log (ε-1 log K) ) time, improving on the algorithm of Badanidiyuru and Vondrak that takes O (nε-1 log (ε-1K) ) time.
AN1009593X
研究報告アルゴリズム（AL）
2018-AL-170
14
1-4
2018-11-05
2188-8566