Streaming algorithms for robust submodular maximization

DOI10.1016/J.DAM.2020.05.001MaRDI QIDQ827610zbMATH OpenOpenAlexFDO

Authors Ruiqi Yang, Yishui Wang, Dongmei Zhang, Dachuan Xu, Yu-kun Cheng

Publication date 13 January 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2020.05.001

zbMATH Keywords

performance guaranteesliding windowsstreaming robust submodular maximization

Mathematics Subject Classification ID

Robustness in mathematical programming (90C17) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• A survey on streaming algorithms for maximizing submodular functions
• Approximating robust parameterized submodular function maximization in large-scales
• Non-submodular maximization on massive data streams
• Streaming algorithms for submodular function maximization

Cites work

• A threshold of ln n for approximating set cover
• An analysis of approximations for maximizing submodular set functions—I
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5968956 (Why is no real title available?)
• Maintaining Stream Statistics over Sliding Windows
• Robust monotone submodular function maximization

Cited in

(17)

• Streaming submodular maximization under differential privacy noise
• Submodular maximization over data streams with differential privacy noise
• Streaming adaptive submodular maximization
• scientific article; zbMATH DE number 6905172 (Why is no real title available?)
• Robust monotone submodular function maximization
• Robust submodular minimization with applications to cooperative modeling
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• The power of subsampling in submodular maximization
• A survey on streaming algorithms for maximizing submodular functions
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Approximating robust parameterized submodular function maximization in large-scales
• Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
• Semi-streaming algorithms for submodular matroid intersection
• Semi-streaming algorithms for submodular matroid intersection
• Streaming submodular maximization with the chance constraint
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• The K-prize-collecting coverage problem by aligned disks

This page was built for publication: Streaming algorithms for robust submodular maximization

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