Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint.

Chien-Chung Huang Naonori Kakimura

Published in: Algorithmica (2021)

Keyphrases

upper bound
submodular functions
worst case
greedy algorithm
learning algorithm
special case
dynamic programming
combinatorial optimization
knapsack problem