An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation

DOI10.1137/1.9781611975482.19zbMath1431.68144arXiv1804.06355OpenAlexW2796716148MaRDI QIDQ5236200

Eric Balkanski, Yaron Singer, Aviad Rubinstein

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

Mathematics Subject Classification ID

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

Related Items (24)

The Limitations of Optimization from Samples ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ Two-stage stochastic max-weight independent set problems ⋮ 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 ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ An optimal streaming algorithm for non-submodular functions maximization on the integer lattice ⋮ Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity ⋮ A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Parallelized maximization of nonsubmodular function subject to a cardinality constraint ⋮ Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint ⋮ Fast algorithms for maximizing monotone nonsubmodular functions ⋮ 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 ⋮ The submodularity of two-stage stochastic maximum-weight independent set problems ⋮ Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy ⋮ An adaptive algorithm for maximization of non-submodular function with a matroid constraint ⋮ Streaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer Lattice ⋮ 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: An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation