Parallelized maximization of nonsubmodular function subject to a cardinality constraint

DOI10.1016/J.TCS.2021.02.035MaRDI QIDQ5925506zbMATH OpenOpenAlexFDO

Authors Hongxiang Zhang, Dachuan Xu, Longkun Guo, Jingjing Tan

Publication date 8 April 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.02.035

zbMATH Keywords

continuous generic submodularity ratiomultilinear relaxationnonsubmodular

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• 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
• Submodular maximization with matroid and packing constraints in parallel
• Parallelizing greedy for submodular set function maximization in matroids and beyond

Cites work

• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• An analysis of approximations for maximizing submodular set functions—I
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Correlation inequalities on some partially ordered sets
• Efficient Submodular Function Maximization under Linear Packing Constraints
• Maximizing a monotone submodular function subject to a matroid constraint
• 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
• Submodular function maximization in parallel via the multilinear relaxation
• Submodular function maximization via the multilinear relaxation and contention resolution schemes
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• Submodularity and randomized rounding techniques for optimal experimental design
• The adaptive complexity of maximizing a submodular function

Cited in

(4)

• Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
• Submodular function maximization in parallel via the multilinear relaxation
• 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

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

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