Streaming submodular maximization under \(d\)-knapsack constraints

DOI10.1007/s10878-022-00951-1OpenAlexW4320058079MaRDI QIDQ2682804

Bin Liu, Zihan Chen, Hongmin W. Du

Publication date: 1 February 2023

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00951-1

zbMATH Keywords

noiseinteger latticestreaming algorithm\(d\)-knapsack constraints

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Discrete convex analysis
• A note on maximizing a submodular set function subject to a knapsack constraint
• Maximizing monotone submodular functions over the integer lattice
• Submodular functions and optimization.
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• An analysis of approximations for maximizing submodular set functions—I
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Online Submodular Maximization with Preemption
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Online submodular welfare maximization: Greedy is optimal
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint