The adaptive complexity of maximizing a submodular function

DOI10.1145/3188745.3188752zbMath1427.68365OpenAlexW2809318113MaRDI QIDQ5230369

Eric Balkanski, Yaron Singer

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188752

zbMATH Keywords

adaptivityparallel algorithmsadaptive samplingsubmodular optimization

Mathematics Subject Classification ID

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

Related Items (20)

The Limitations of Optimization from Samples ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ 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 ⋮ Deterministic approximation algorithm for submodular maximization subject to a matroid constraint ⋮ 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 ⋮ 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 ⋮ 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 ⋮ 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: The adaptive complexity of maximizing a submodular function