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

DOI10.1137/1.9781611975482.18MaRDI QIDQ5236199zbMATH OpenOpenAlexFDO

Authors

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

Mathematics Subject Classification ID

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

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))$.

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

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
• Partial-monotone adaptive submodular maximization
• Adaptive algorithms on maximizing monotone nonsubmodular functions
• Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
• 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
• Submodular maximization with matroid and packing constraints in parallel
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• 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
• Adaptive robust submodular optimization and beyond
• Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
• Unconstrained submodular maximization with constant adaptive complexity
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• Parallelized maximization of nonsubmodular function subject to a cardinality constraint
• 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 monotone non-submodular function maximization under a knapsack constraint on the integer lattice
• Streaming algorithms for non-submodular functions maximization with \(d\)-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)