Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity

DOI10.1137/1.9781611975482.17zbMath1431.68131arXiv1807.07889OpenAlexW2883693373MaRDI QIDQ5236198

Matthew Fahrbach, Morteza Zadimoghaddam, Vahab S. Mirrokni

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.07889

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (14)

The Limitations of Optimization from Samples ⋮ An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model ⋮ A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions ⋮ A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems ⋮ Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ 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 ⋮ Unnamed Item ⋮ 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 ⋮ 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

This page was built for publication: Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity