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 SamplesAn Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity ModelMaximization of monotone non-submodular functions with a knapsack constraint over the integer latticeBi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraintAn optimal streaming algorithm for non-submodular functions maximization on the integer latticeAlgorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexityA note for approximating the submodular cover problem over integer lattice with low adaptive and query complexitiesParallelized maximization of nonsubmodular function subject to a cardinality constraintApproximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraintFast algorithms for maximizing monotone nonsubmodular functionsApproximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraintParallelized maximization of nonsubmodular function subject to a cardinality constraintImproved streaming algorithms for maximizing monotone submodular functions under a knapsack constraintMulti-pass streaming algorithms for monotone submodular function maximizationStreaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer latticeAn adaptive algorithm for maximization of non-submodular function with a matroid constraintStreaming Algorithms for Maximizing Monotone DR-Submodular Functions with a Cardinality Constraint on the Integer LatticeRandomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality ConstraintApproximability 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