Submodular maximization with matroid and packing constraints in parallel

DOI10.1145/3313276.3316389MaRDI QIDQ5212750zbMATH OpenOpenAlexFDO

Authors

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.09987

zbMATH Keywords

DR-submodular maximizationmatroidpackingparallel complexity

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Approximation algorithms (68W25) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: We consider the problem of maximizing the multilinear extension of a submodular function subject a single matroid constraint or multiple packing constraints with a small number of adaptive rounds of evaluation queries. We obtain the first algorithms with low adaptivity for submodular maximization with a matroid constraint. Our algorithms achieve a $1-1/e-epsilon$ approximation for monotone functions and a $1/e-epsilon$ approximation for non-monotone functions, which nearly matches the best guarantees known in the fully adaptive setting. The number of rounds of adaptivity is $O(lo{g}^{2}n/epsilo{n}^3)$, which is an exponential speedup over the existing algorithms. We obtain the first parallel algorithm for non-monotone submodular maximization subject to packing constraints. Our algorithm achieves a $1/e-epsilon$ approximation using $O(log(n/epsilon)log(1/epsilon)log(n+m)/epsilo{n}^2)$ parallel rounds, which is again an exponential speedup in parallel time over the existing algorithms. For monotone functions, we obtain a $1-1/e-epsilon$ approximation in $O(log(n/epsilon)log(m)/epsilo{n}^2)$ parallel rounds. The number of parallel rounds of our algorithm matches that of the state of the art algorithm for solving packing LPs with a linear objective. Our results apply more generally to the problem of maximizing a diminishing returns submodular (DR-submodular) function.

Recommendations

• Submodular function maximization in parallel via the multilinear relaxation
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

Cited in

(21)

• Efficient Submodular Function Maximization under Linear Packing Constraints
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• A lower bound for parallel submodular minimization
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• 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
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities
• Subquadratic submodular maximization with a general matroid constraint
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Deletion robust non-monotone submodular maximization over matroids
• A differentially private approximation algorithm for submodular maximization under a polymatroid constraint over the integer lattice
• Practical parallel algorithms for non-monotone submodular maximization
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Practical algorithm for minimum cost submodular cover problem with performance guarantees
• Parallelizing scheduling algorithms for resource allocation under V-RAN
• Parallel approximation and exact algorithms for resource scheduling in v-RANs

This page was built for publication: Submodular maximization with matroid and packing constraints in parallel

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