Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint

DOI10.1142/S0217595921400091MaRDI QIDQ5024901zbMATH OpenOpenAlexFDO

Authors Jingjing Tan, Wen-Ting Chen, Meixia Li, Wenchao Wang

Publication date 1 February 2022

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

cardinalityrandomized parallel algorithmmultilinear relaxationnonsubmodular function

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Fast algorithms for maximizing monotone nonsubmodular functions

Cites work

• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• scientific article; zbMATH DE number 1445291 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• An analysis of approximations for maximizing submodular set functions—I
• Approximating robust parameterized submodular function maximization in large-scales
• Maximizing a monotone submodular function subject to a matroid constraint
• Non-submodular maximization on massive data streams
• On multiplicative weight updates for concave and submodular function maximization
• Optimal approximation for the submodular welfare problem in the value oracle model
• Parametric monotone function maximization with matroid constraints
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Submodular function maximization in parallel via the multilinear relaxation
• Submodularity and randomized rounding techniques for optimal experimental design
• The adaptive complexity of maximizing a submodular function

Cited in

(2)

• scientific article; zbMATH DE number 1003294 (Why is no real title available?)
• Fast deterministic algorithms for non-submodular maximization with strong performance guarantees

This page was built for publication: Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint

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