Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions

DOI10.1142/S0129054123410083MaRDI QIDQ6610086zbMATH OpenFDO

Authors Min Cui, Donglei Du, Ling Gai, Ruiqi Yang

Publication date 24 September 2024

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054123410083

zbMATH Keywords

cardinality-constrainedlinear-timestreaming

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Recommendations

• Multi-pass streaming algorithms for monotone submodular function maximization
• An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 5485445 (Why is no real title available?)
• scientific article; zbMATH DE number 7788452 (Why is no real title available?)
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• An analysis of approximations for maximizing submodular set functions—I
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Best Algorithms for Approximating the Maximum of a Submodular Set Function
• Data streams: algorithms and applications.
• Fast algorithms for maximizing monotone nonsubmodular functions
• Maximize a monotone function with a generic submodularity ratio
• Maximizing Non-monotone Submodular Functions
• Non-submodular maximization on massive data streams
• Non-submodular streaming maximization with minimum memory and low adaptive complexity
• Online submodular maximization with preemption
• Parametric monotone function maximization with matroid constraints
• Streaming algorithms for robust submodular maximization
• Submodular function maximization in parallel via the multilinear relaxation
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

This page was built for publication: Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions

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