Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Chien Chung Huang; Naonori Kakimura

doi:10.1007/978-3-030-24766-9_32

Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Chien Chung Huang, Naonori Kakimura

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Original language	English
Title of host publication	Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings
Editors	Zachary Friggstad, Mohammad R. Salavatipour, Jörg-Rüdiger Sack
Publisher	Springer Verlag
Pages	438-451
Number of pages	14
ISBN (Print)	9783030247652
DOIs	https://doi.org/10.1007/978-3-030-24766-9_32
Publication status	Published - 2019
Event	16th International Symposium on Algorithms and Data Structures, WADS 2019 - Edmonton, Canada Duration: 2019 Aug 5 → 2019 Aug 7

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11646 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Symposium on Algorithms and Data Structures, WADS 2019
Country/Territory	Canada
City	Edmonton
Period	19/8/5 → 19/8/7

Keywords

Approximation algorithm
Streaming algorithm
Submodular functions

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-24766-9_32

Cite this

Huang, C. C., & Kakimura, N. (2019). Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. In Z. Friggstad, M. R. Salavatipour, & J.-R. Sack (Eds.), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings (pp. 438-451). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11646 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-24766-9_32

Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. / Huang, Chien Chung; Kakimura, Naonori.
Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings. ed. / Zachary Friggstad; Mohammad R. Salavatipour; Jörg-Rüdiger Sack. Springer Verlag, 2019. p. 438-451 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11646 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Huang, CC & Kakimura, N 2019, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. in Z Friggstad, MR Salavatipour & J-R Sack (eds), Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11646 LNCS, Springer Verlag, pp. 438-451, 16th International Symposium on Algorithms and Data Structures, WADS 2019, Edmonton, Canada, 19/8/5. https://doi.org/10.1007/978-3-030-24766-9_32

Huang CC, Kakimura N. Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. In Friggstad Z, Salavatipour MR, Sack JR, editors, Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings. Springer Verlag. 2019. p. 438-451. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-24766-9_32

Huang, Chien Chung ; Kakimura, Naonori. / Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings. editor / Zachary Friggstad ; Mohammad R. Salavatipour ; Jörg-Rüdiger Sack. Springer Verlag, 2019. pp. 438-451 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d4e26cae58e145e18c525372ffa54a12,

title = "Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint",

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

keywords = "Approximation algorithm, Streaming algorithm, Submodular functions",

author = "Huang, {Chien Chung} and Naonori Kakimura",

note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 16th International Symposium on Algorithms and Data Structures, WADS 2019 ; Conference date: 05-08-2019 Through 07-08-2019",

year = "2019",

doi = "10.1007/978-3-030-24766-9_32",

language = "English",

isbn = "9783030247652",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "438--451",

editor = "Zachary Friggstad and Salavatipour, {Mohammad R.} and J{\"o}rg-R{\"u}diger Sack",

booktitle = "Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings",

}

TY - GEN

T1 - Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

AU - Huang, Chien Chung

AU - Kakimura, Naonori

N1 - Publisher Copyright: © Springer Nature Switzerland AG 2019.

PY - 2019

Y1 - 2019

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

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

KW - Approximation algorithm

KW - Streaming algorithm

KW - Submodular functions

UR - http://www.scopus.com/inward/record.url?scp=85070651832&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85070651832&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-24766-9_32

DO - 10.1007/978-3-030-24766-9_32

M3 - Conference contribution

AN - SCOPUS:85070651832

SN - 9783030247652

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 438

EP - 451

BT - Algorithms and Data Structures - 16th International Symposium, WADS 2019, Proceedings

A2 - Friggstad, Zachary

A2 - Salavatipour, Mohammad R.

A2 - Sack, Jörg-Rüdiger

PB - Springer Verlag

T2 - 16th International Symposium on Algorithms and Data Structures, WADS 2019

Y2 - 5 August 2019 through 7 August 2019

ER -

Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this