Streaming submodular maximization with the chance constraint

DOI10.1007/978-3-031-20796-9_10MaRDI QIDQ6166877zbMATH OpenFDO

Authors Shufang Gong, Bin Liu, Qizhi Fang

Publication date 3 August 2023

Published in Frontiers of Algorithmic Wisdom (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-20796-9_10

zbMATH Keywords

streaming algorithmsubmodular maximizationchance constraint

Mathematics Subject Classification ID

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

Recommendations

• A survey on streaming algorithms for maximizing submodular functions
• Streaming algorithms for robust submodular maximization
• Streaming algorithms for submodular function maximization
• Streaming submodular maximization under \(d\)-knapsack constraints
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• A One-Sided Inequality of the Chebyshev Type
• A guided tour of Chernoff bounds
• A note on maximizing a submodular set function subject to a knapsack constraint
• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• Approximation with a fixed number of solutions of some multiobjective maximization problems
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Exploiting structure of chance constrained programs via submodularity
• Gadgets, Approximation, and Linear Programming
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Non-submodular maximization on massive data streams
• Robust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularity
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for submodular function maximization
• The budgeted maximum coverage problem
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

Cited in

(3)

• Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
• Streaming submodular maximization under differential privacy noise
• Streaming submodular maximization under \(d\)-knapsack constraints

This page was built for publication: Streaming submodular maximization with the chance constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166877)