Submodular function maximization in parallel via the multilinear relaxation

DOI10.1137/1.9781611975482.20MaRDI QIDQ5236201zbMATHOpenAlexFDO

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

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

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

(27)

• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Online learning under one sided \(\sigma\)-smooth function
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• On multiplicative weight updates for concave and submodular function maximization
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Submodular maximization with matroid and packing constraints in parallel
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Multi-pass streaming algorithms for monotone submodular function maximization
• Parallelizing greedy for submodular set function maximization in matroids and beyond
• The Limitations of Optimization from Samples
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Online one-sided smooth function maximization
• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• scientific article; zbMATH DE number 7626767 (Why is no real title available?)
• 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
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint

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)