Practical parallel algorithms for non-monotone submodular maximization

DOI10.1613/JAIR.1.16801MaRDI QIDQ7014324zbMATH OpenFDO

Authors Shuang Cui, Kai Han, Jing Tang, Xueying Li, Aakas Zhiyuli, Hanxiao Li

Publication date 11 March 2025

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/JAIR.1.16801

zbMATH Keywords

nonmonotone submodular maximizationparallel algorithm

Mathematics Subject Classification ID

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

Cites work

• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• A note on maximizing a submodular set function subject to a knapsack constraint
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
• Comparing apples and oranges: query tradeoff in submodular maximization
• Constrained submodular maximization via a nonsymmetric technique
• Determinantal point processes for machine learning
• Distributed submodular maximization
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 5485514 (Why is no real title available?)
• scientific article; zbMATH DE number 3580314 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing Non-monotone Submodular Functions
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
• Maximizing submodular set functions subject to multiple linear constraints
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• Submodular function maximization in parallel via the multilinear relaxation
• Submodular maximization with cardinality constraints
• Submodular maximization with matroid and packing constraints in parallel
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
• The adaptive complexity of maximizing a submodular function
• Unconstrained submodular maximization with constant adaptive complexity

Cited in

(1)

• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity

This page was built for publication: Practical parallel algorithms for non-monotone submodular maximization

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