An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
From MaRDI portal
Publication:5058055
DOI10.1287/opre.2021.2170OpenAlexW2900404942MaRDI QIDQ5058055
Yaron Singer, Aviad Rubinstein, Eric Balkanski
Publication date: 1 December 2022
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.2021.2170
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular maximization meets streaming: matchings, matroids, and more
- Communication complexity
- The complexity of parallel search
- A note on maximizing a submodular set function subject to a knapsack constraint
- Practical budgeted submodular maximization
- Randomized Composable Core-sets for Distributed Submodular Maximization
- On Multiplicative Weight Updates for Concave and Submodular Function Maximization
- Parallel Merge Sort
- Parallelism in Comparison Problems
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs
- Parallelizing greedy for submodular set function maximization in matroids and beyond
- Submodular maximization with matroid and packing constraints in parallel
- The adaptive complexity of maximizing a submodular function
- Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Submodular Function Maximization in Parallel via the Multilinear Relaxation
- Parallel algorithms for select and partition with noisy comparisons
- Online Submodular Maximization with Preemption
- Fast algorithms for maximizing submodular functions
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- On the Power of Adaptivity in Sparse Recovery
This page was built for publication: An Optimal Approximation for Submodular Maximization Under a Matroid Constraint in the Adaptive Complexity Model
