Parallelizing greedy for submodular set function maximization in matroids and beyond

DOI10.1145/3313276.3316406MaRDI QIDQ5212749zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kent Quanrud

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/1811.12568

zbMATH Keywords

matroidsparallel algorithmssubmodular maximization

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: We consider parallel, or low adaptivity, algorithms for submodular function maximization. This line of work was recently initiated by Balkanski and Singer and has already led to several interesting results on the cardinality constraint and explicit packing constraints. An important open problem is the classical setting of matroid constraint, which has been instrumental for developments in submodular function maximization. In this paper we develop a general strategy to parallelize the well-studied greedy algorithm and use it to obtain a randomized $left(frac12-epsilonight)$-approximation in $operatornameOleft(fraclo{g}^{2}nepsilo{n}^{2}ight)$ rounds of adaptivity. We rely on this algorithm, and an elegant amplification approach due to Badanidiyuru and Vondr'ak to obtain a fractional solution that yields a near-optimal randomized $left(1-1/e-epsilonight)$-approximation in $Oleft(fraclo{g}^{2}nepsilo{n}^{3}ight)$ rounds of adaptivity. For non-negative functions we obtain a $left(3-2sqrt2ight)$-approximation and a fractional solution that yields a $left(frac1e-epsilonight)$-approximation. Our approach for parallelizing greedy yields approximations for intersections of matroids and matchoids, and the approximation ratios are comparable to those known for sequential greedy.

Recommendations

• Submodular maximization with matroid and packing constraints in parallel
• Submodular function maximization in parallel via the multilinear relaxation
• 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
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint

Cited in

(20)

• The submodularity of two-stage stochastic maximum-weight independent set problems
• Two-stage stochastic max-weight independent set problems
• On parallelizing a greedy heuristic for finding small dominant sets
• Non-submodular maximization with matroid and knapsack constraints
• scientific article; zbMATH DE number 7626767 (Why is no real title available?)
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Submodular maximization with matroid and packing constraints in parallel
• 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
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Subquadratic submodular maximization with a general matroid constraint
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Practical parallel algorithms for non-monotone submodular maximization
• Streaming algorithms for maximizing k-submodular functions with the multi-knapsack constraint
• 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: Parallelizing greedy for submodular set function maximization in matroids and beyond

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