http://swrc.ontoware.org/ontology#TechnicalReport
Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint
en
CNRS, École Normale Supérieure
Department of Mathematics, Keio University
Chien-Chung Huang
Naonori Kakimura
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 ε.
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-174
6
1-4
2019-09-10
2188-8566