Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

DOI10.1007/s00453-019-00628-yzbMath1435.68389OpenAlexW4246587691WikidataQ127252149 ScholiaQ127252149MaRDI QIDQ2300732

Yuichi Yoshida, Naonori Kakimura, Chien-Chung Huang

Publication date: 28 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/7560/

zbMATH Keywords

submodular functionsconstant approximationmultiple-pass streamingsingle-pass streaming

Mathematics Subject Classification ID

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

Related Items (7)

Submodular Maximization Subject to a Knapsack Constraint Under Noise Models ⋮ Maximizing \(k\)-submodular functions under budget constraint: applications and streaming algorithms ⋮ Streaming submodular maximization with the chance constraint ⋮ Sequence submodular maximization meets streaming ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model

Cites Work

• Submodular maximization meets streaming: matchings, matroids, and more
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Streaming Algorithms for Submodular Function Maximization
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Online Submodular Maximization with Free Disposal: Randomization Beats ¼ for Partition Matroids
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Fast algorithms for maximizing submodular functions
• Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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