2021-06-23T09:46:20Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001990932020-04-01T00:33:29Z01164:02592:09674:09895
Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack ConstraintImproved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraintenghttp://id.nii.ac.jp/1001/00199003/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=199093&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Information Processing Society of JapanCNRS, École Normale SupérieureDepartment of Mathematics, Keio UniversityChien-Chung, HuangNaonori, KakimuraIn this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - ε)-approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - ε)-approximation algorithm. The required memory space depends only on the size of the knapsack capacity and ε.In this paper, we consider the problem of maximizing a monotone submodular function subject to a knapsack constraint in the streaming setting. In particular, the elements arrive sequentially and at any point of time, the algorithm has access only to a small fraction of the data stored in primary memory. For this problem, we propose a (0.4 - ε)-approximation algorithm requiring only a single pass through the data. This improves on the currently best (0.363 - ε)-approximation algorithm. The required memory space depends only on the size of the knapsack capacity and ε.AN1009593X研究報告アルゴリズム（AL）2019-AL-1746142019-09-102188-85662019-09-04