Submodular maximization with nearly optimal approximation, adaptivity and query complexity
From MaRDI portal
Abstract: Submodular optimization generalizes many classic problems in combinatorial optimization and has recently found a wide range of applications in machine learning (e.g., feature engineering and active learning). For many large-scale optimization problems, we are often concerned with the adaptivity complexity of an algorithm, which quantifies the number of sequential rounds where polynomially-many independent function evaluations can be executed in parallel. While low adaptivity is ideal, it is not sufficient for a distributed algorithm to be efficient, since in many practical applications of submodular optimization the number of function evaluations becomes prohibitively expensive. Motivated by these applications, we study the adaptivity and query complexity of adaptive submodular optimization. Our main result is a distributed algorithm for maximizing a monotone submodular function with cardinality constraint that achieves a -approximation in expectation. This algorithm runs in adaptive rounds and makes calls to the function evaluation oracle in expectation. The approximation guarantee and query complexity are optimal, and the adaptivity is nearly optimal. Moreover, the number of queries is substantially less than in previous works. Last, we extend our results to the submodular cover problem to demonstrate the generality of our algorithm and techniques.
Recommendations
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- The adaptive complexity of maximizing a submodular function
- 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
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Cited in
(41)- Pareto optimization for subset selection with dynamic cost constraints
- Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
- A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems
- Randomized composable core-sets for distributed submodular maximization
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- Submodular Approximation: Sampling-based Algorithms and Lower Bounds
- scientific article; zbMATH DE number 7051222 (Why is no real title available?)
- scientific article; zbMATH DE number 6999915 (Why is no real title available?)
- The limitations of optimization from samples
- Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
- scientific article; zbMATH DE number 7626767 (Why is no real title available?)
- An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
- Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
- 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
- Unconstrained submodular maximization with constant adaptive complexity
- The adaptive complexity of maximizing a submodular function
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Optimization with uniform size queries
- New Query Lower Bounds for Submodular Function Minimization
- The Limitations of Optimization from Samples
- 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
- 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
- Adaptive algorithms on maximizing monotone nonsubmodular functions
- Fast parallel algorithms for submodular \(p\)-superseparable maximization
- Submodular optimization in the MapReduce model
- Scalable distributed algorithms for size-constrained submodular maximization in the MapReduce and adaptive complexity models
- Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
- Submodular maximization subject to a knapsack constraint: combinatorial algorithms with near-optimal adaptive complexity
- Efficient parallel algorithm for minimum cost submodular cover problem with lower 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
- Practical algorithm for minimum cost submodular cover problem with performance guarantees
- Cut-query algorithms with few rounds
- Dynamic algorithms for submodular matching
This page was built for publication: Submodular maximization with nearly optimal approximation, adaptivity and query complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236198)
