Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint

DOI10.1142/S0217595921400091OpenAlexW3135659653MaRDI QIDQ5024901

Meixia Li, Wen-Ting Chen, Jingjing Tan, 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

randomized parallel algorithmcardinalitymultilinear relaxationnonsubmodular function

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Parametric monotone function maximization with matroid constraints
• Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint
• Non-submodular maximization on massive data streams
• Submodularity and Randomized rounding techniques for Optimal Experimental Design
• On Multiplicative Weight Updates for Concave and Submodular Function Maximization
• A threshold of ln n for approximating set cover
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Approximating Robust Parameterized Submodular Function Maximization in Large-Scales
• The adaptive complexity of maximizing a submodular function
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Function Maximization in Parallel via the Multilinear Relaxation
• Unnamed Item
• Unnamed Item
• Unnamed Item

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