Submodular function maximization in parallel via the multilinear relaxation

DOI10.1137/1.9781611975482.20MaRDI QIDQ5236201zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Kent Quanrud

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Balkanski and Singer [5] recently initiated the study of adaptivity (or parallelism) for constrained submodular function maximization, and studied the setting of a cardinality constraint. Very recent improvements for this problem by Balkanski, Rubinstein, and Singer [6] and Ene and Nguyen [21] resulted in a near-optimal $(1-1/e-epsilon)$-approximation in $O(logn/epsilo{n}^2)$ rounds of adaptivity. Partly motivated by the goal of extending these results to more general constraints, we describe parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to packing constraints. Formally our problem is to maximize $F(x)$ over $xin[0,1{]}^n$ subject to $Axle1$ where $F$ is the multilinear relaxation of a monotone submodular function. Our algorithm achieves a near-optimal $(1-1/e-epsilon)$-approximation in $O(lo{g}^{2}mlogn/epsilo{n}^4)$ rounds where $n$ is the cardinality of the ground set and $m$ is the number of packing constraints. For many constraints of interest, the resulting fractional solution can be rounded via known randomized rounding schemes that are oblivious to the specific submodular function. We thus derive randomized algorithms with poly-logarithmic adaptivity for a number of constraints including partition and laminar matroids, matchings, knapsack constraints, and their intersections.

Recommendations

• Submodular maximization with matroid and packing constraints in parallel
• 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
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint

Cited in

(32)

• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• On multiplicative weight updates for concave and submodular function maximization
• Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• 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
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• Submodular maximization with matroid and packing constraints in parallel
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• The Limitations of Optimization from Samples
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• 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
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Online one-sided smooth function maximization
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• Online learning under one sided -smooth function
• Concentration of submodular functions and read-k families under negative dependence
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Properties and algorithm of lattice pseudo-submodular functions
• Practical parallel algorithms for non-monotone submodular maximization
• The one-way communication complexity of submodular maximization with applications to streaming and robustness

This page was built for publication: Submodular function maximization in parallel via the multilinear relaxation

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