Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint

Chien Chung Huang, Naonori Kakimura, Yuichi Yoshida

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

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 ε.

Original languageEnglish
Pages (from-to)1006-1032
Number of pages27
JournalAlgorithmica
Volume82
Issue number4
DOIs
Publication statusPublished - 2020 Apr 1

Keywords

  • Constant approximation
  • Multiple-pass streaming
  • Single-pass streaming
  • Submodular functions

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint'. Together they form a unique fingerprint.

Cite this