Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
From MaRDI portal
Publication:5236199
DOI10.1137/1.9781611975482.18zbMath1431.68152arXiv1804.05379OpenAlexW2797074460MaRDI QIDQ5236199
No author found.
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.05379
Related Items (19)
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 ⋮ 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 ⋮ 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 ⋮ 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: Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
