2021-06-23T09:33:49Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001917192020-04-01T00:33:29Z01164:02592:09368:09571
Multi-Pass Streaming Algorithms for Monotone Submodular Function MaximizationMulti-Pass Streaming Algorithms for Monotone Submodular Function Maximizationenghttp://id.nii.ac.jp/1001/00191630/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=191719&item_no=1&attribute_id=1&file_no=1Copyright (c) 2018 by the Information Processing Society of JapanCNRS, Ecole Normale SuperieureDepartment of Mathematics, Keio UniversityChien-Chung, HuangNaonori, KakimuraWe 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-17014142018-11-052188-85662018-10-24