Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

DOI10.1137/1.9781611975482.18zbMATH Open1431.68152arXiv1804.05379OpenAlexW2797074460MaRDI QIDQ5236199FDOQ5236199

Authors:

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In this paper, we study the tradeoff between the approximation guarantee and adaptivity for the problem of maximizing a monotone submodular function subject to a cardinality constraint. The adaptivity of an algorithm is the number of sequential rounds of queries it makes to the evaluation oracle of the function, where in every round the algorithm is allowed to make polynomially-many parallel queries. Adaptivity is an important consideration in settings where the objective function is estimated using samples and in applications where adaptivity is the main running time bottleneck. Previous algorithms achieving a nearly-optimal $1-1/e-epsilon$ approximation require $Omega(n)$ rounds of adaptivity. In this work, we give the first algorithm that achieves a $1-1/e-epsilon$ approximation using $O(lnn/epsilo{n}^2)$ rounds of adaptivity. The number of function evaluations and additional running time of the algorithm are $O(nmathrmpoly(logn,1/epsilon))$.

Full work available at URL: https://arxiv.org/abs/1804.05379

Recommendations

• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• A tight linear time (1/2)-approximation for unconstrained submodular maximization
• Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
• Unconstrained submodular maximization with constant adaptive complexity
• Partial-adaptive submodular maximization
• A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
• The adaptive complexity of maximizing a submodular function

Mathematics Subject Classification ID

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

Cited In (34)

• An adaptive algorithm for maximization of non-submodular function with a matroid constraint
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Adaptive algorithms on maximizing monotone nonsubmodular functions
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• Partial-monotone adaptive submodular maximization
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• Submodular maximization with matroid and packing constraints in parallel
• Pareto optimization for subset selection with dynamic cost constraints
• Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint
• A note for approximating the submodular cover problem over integer lattice with low adaptive and query complexities
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
• The adaptive complexity of maximizing a submodular function
• The Limitations of Optimization from Samples
• Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
• Bi-criteria adaptive algorithms for minimizing supermodular functions with cardinality constraint
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Adaptive robust submodular optimization and beyond
• Unconstrained submodular maximization with constant adaptive complexity
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• 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
• Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint
• Multi-pass streaming algorithms for monotone submodular function maximization
• Fast algorithms for maximizing monotone nonsubmodular functions
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time

This page was built for publication: Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236199)