Parallelized maximization of nonsubmodular function subject to a cardinality constraint

DOI10.1007/978-3-030-58150-3_42OpenAlexW3082082684MaRDI QIDQ5918257

Longkun Guo, Jingjing Tan, Da-Chuan Xu, Hongxiang Zhang

Publication date: 21 April 2021

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_42

zbMATH Keywords

parallel algorithmcardinality constraintsmultilinear relaxationnonsubmodular

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Unnamed Item
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Correlation inequalities on some partially ordered sets
• Parametric monotone function maximization with matroid constraints
• Submodularity and Randomized rounding techniques for Optimal Experimental Design
• On Multiplicative Weight Updates for Concave and Submodular Function Maximization
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• An analysis of approximations for maximizing submodular set functions—I
• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• 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

This page was built for publication: Parallelized maximization of nonsubmodular function subject to a cardinality constraint