Research map / Learning theory and algorithms / Submodular and game algorithms
The FAST Algorithm for Submodular Maximization
Adam Breuer, Eric Balkanski, Yaron Singer
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Fast instead of Exhaustive-Maximization | Submodular maximization · Watts-Strogatz max-cover (n=500) | time (sec): 55.14 -> 0.051 | Improved |
| Use Fast instead of Amortized-Filtering | Submodular maximization · Watts-Strogatz max-cover (n=500) | time (sec): 0.58 -> 0.051 | Improved |
| Use Fast instead of Randomized-Parallel-Greedy | Submodular maximization · Watts-Strogatz max-cover (n=500) | time (sec): 1.36 -> 0.051 | Improved |
| Use Fast instead of Parallel-LTLG | Submodular maximization · Eight synthetic and real-data objectives, k from 25 to 25000 | runtime: 1.5 to 27 times faster | Improved |
| Use Fast instead of Parallel-LTLG | Submodular maximization · Eight large synthetic and real-data experiments | solution value | Improved |
| Use Fast instead of low-adaptivity baselines | Submodular maximization · Eight synthetic and real-data objectives | runtime: 18 to 2800 times faster; 3 to 145 times faster; 8 to 1300 times faster | Improved |
| Use Fast instead of Greedy | Submodular maximization · Experiments on eight objectives | solution value | No clear effect |
Closest papers by meaning
- Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel (NeurIPS 2021 · similarity 0.93)
- Practical Parallel Algorithms for Submodular Maximization Subject to a Knapsack Constraint with Nearly Optimal Adaptivity (AAAI 2023 · similarity 0.92)
- Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (ICML 2019 · similarity 0.92)
- Nearly Linear-Time, Parallelizable Algorithms for Non-Monotone Submodular Maximization (AAAI 2021 · similarity 0.92)
- Breaking Barriers: Combinatorial Algorithms for Non-Monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation (ICML 2025 · similarity 0.90)
- Learning-Augmented Dynamic Submodular Maximization (NeurIPS 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
