Submodular Function Maximization in Parallel via the Multilinear Relaxation

DOI10.1137/1.9781611975482.20zbMath1431.68148arXiv1807.08678OpenAlexW2952567852MaRDI QIDQ5236201

Kent Quanrud, Chandra Chekuri

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) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (18)

The Limitations of Optimization from Samples ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ 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 ⋮ Online one-sided smooth function maximization ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ Unnamed Item ⋮ 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 ⋮ 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 ⋮ 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

This page was built for publication: Submodular Function Maximization in Parallel via the Multilinear Relaxation