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

DOI10.1007/978-3-030-24766-9_32zbMath1435.68388OpenAlexW2965391966MaRDI QIDQ5919318

Chien-Chung Huang, Naonori Kakimura

Publication date: 16 January 2020

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-24766-9_32

zbMATH Keywords

approximation algorithmsubmodular functionsstreaming algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (5)

Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice ⋮ On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice ⋮ Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

This page was built for publication: Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint