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

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

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

(42)

• Adaptive robust submodular optimization and beyond
• Pareto optimization for subset selection with dynamic cost constraints
• 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
• Partial-monotone adaptive submodular maximization
• 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
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
• Discrete stochastic submodular maximization: adaptive vs. non-adaptive vs. offline
• 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
• An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
• A polynomial lower bound on adaptive complexity of submodular maximization
• An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model
• Submodular maximization with matroid and packing constraints in parallel
• Unconstrained submodular maximization with constant adaptive complexity
• The adaptive complexity of maximizing a submodular function
• Submodular maximization with nearly optimal approximation, adaptivity and query complexity
• An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
• The Limitations of Optimization from Samples
• 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
• 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
• Streaming algorithms for non-submodular functions maximization with \(d\)-knapsack constraint on the Integer lattice
• Adaptive algorithms on maximizing monotone nonsubmodular functions
• Fast parallel algorithms for submodular \(p\)-superseparable maximization
• Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
• Subquadratic submodular maximization with a general matroid constraint
• Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
• Practical parallel algorithms for non-monotone submodular maximization
• The one-way communication complexity of submodular maximization with applications to streaming and robustness
• Improved approximation factor for adaptive influence maximization via simple greedy strategies
• Maximizing the difference of DR-submodular function on the integer lattice
• Cut-query algorithms with few rounds

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)