Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
From MaRDI portal
Publication:5236198
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
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