TY - GEN
T1 - Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
AU - Huang, Chien Chung
AU - Kakimura, Naonori
AU - Yoshida, Yuichi
N1 - Funding Information:
∗ A full version of the paper is available at http://www.di.ens.fr/~cchuang/work/streaming_knapsack. pdf. † Partly supported by JST ERATO Grant Number JPMJER1305, and JSPS KAKENHI Grant Number JP17K00028. ‡ Partly supported by JST ERATO Grant Number JPMJER1305 and JSPS KAKENHI Grant Number JP17H04676
Publisher Copyright:
© Chien-Chung Huang, Naonori Kakimura, and Yuichi Yoshida.
PY - 2017/8/1
Y1 - 2017/8/1
N2 - 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.363-ϵ)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4 - ϵ)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and ϵ.
AB - 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.363-ϵ)-approximation algorithm, requiring only a single pass through the data; moreover, we propose a (0.4 - ϵ)-approximation algorithm requiring a constant number of passes through the data. The required memory space of both algorithms depends only on the size of the knapsack capacity and ϵ.
KW - Constant approximation
KW - Multiple-pass streaming
KW - Single-pass streaming
KW - Submodular functions
UR - http://www.scopus.com/inward/record.url?scp=85028696138&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85028696138&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX/RANDOM.2017.11
DO - 10.4230/LIPIcs.APPROX/RANDOM.2017.11
M3 - Conference contribution
AN - SCOPUS:85028696138
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 20th International Workshop, APPROX 2017 and 21st International Workshop, RANDOM 2017
A2 - Rolim, Jose D. P.
A2 - Jansen, Klaus
A2 - Williamson, David P.
A2 - Vempala, Santosh S.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2017 and the 21st International Workshop on Randomization and Computation, RANDOM 2017
Y2 - 16 August 2017 through 18 August 2017
ER -