Back to Search
Start Over
Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint.
- Source :
-
Algorithmica . Apr2020, Vol. 82 Issue 4, p1006-1032. 27p. - Publication Year :
- 2020
-
Abstract
- 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 ε . [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBMODULAR functions
*BACKPACKS
*APPROXIMATION algorithms
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 82
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 141917045
- Full Text :
- https://doi.org/10.1007/s00453-019-00628-y