Submodular function maximization in parallel via the multilinear relaxation

DOI10.1137/1.9781611975482.20zbMATH Open1431.68148arXiv1807.08678OpenAlexW2952567852MaRDI QIDQ5236201FDOQ5236201

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (25)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• On multiplicative weight updates for concave and submodular function maximization
• 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
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Online one-sided smooth function maximization
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Title not available (Why is that?)
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• The Limitations of Optimization from Samples
• Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Online learning under one sided \(\sigma\)-smooth function
• Maximization of monotone non-submodular functions with a knapsack constraint over the integer lattice
• Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
• Multi-pass streaming algorithms for monotone submodular function maximization
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice

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)