Research map / Learning theory and algorithms / Submodular and game algorithms
Distributed Submodular Maximization
Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, Andreas Krause
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 GreeDi two-round distributed greedy instead of random/random, random/greedy, greedy/merge and greedy/max | naive distributed baselines · Tiny Images (10,000, k=50) | distributed/centralized objective ratio | Improved |
| use GreeDi with small alpha below 1 | GreeDi · Tiny Images (10,000, k=50) | distributed/centralized objective ratio | No clear effect |
| evaluate objective on local data only instead of global data (decomposable) (ablation) | GreeDi · Tiny Images (10,000, k=50) | distributed/centralized objective ratio | No clear effect |
| use GreeDi instead of distributed benchmarks | naive distributed baselines · Tiny Images 80M (m=8000, k=64) | objective value | Improved |
| use GreeDi instead of benchmarks | naive distributed baselines · Parkinsons Telemonitoring (k=50, m=10) | distributed/centralized objective ratio | Improved |
| use GreeDi instead of benchmarks | naive distributed baselines · Yahoo Webscope (45,811,883 visits, m=32) | objective value | Improved |
| increase number of machines m (ablation) | GreeDi · Yahoo Webscope | speedup over centralized greedy | Mixed |
| use GreeDi with RandomGreedy on non-decomposable cut function instead of benchmarks | naive distributed baselines · Facebook-like network max cut (k=20) | distributed/centralized ratio | Improved |
| use GreeDi instead of GreedyScaling | GreedyScaling · Accidents (340,183 elements) | coverage ratio to centralized | Improved |
| use GreeDi instead of GreedyScaling | GreedyScaling · Kosarak (990,002 elements) | coverage ratio to centralized | No clear effect |
Closest papers by meaning
- Horizontally Scalable Submodular Maximization (ICML 2016 · similarity 0.93)
- DASH: A Distributed and Parallelizable Algorithm for Size-Constrained Submodular Maximization (AAAI 2023 · similarity 0.92)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.89)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.88)
- Decomposable Submodular Maximization in Federated Setting (ICML 2024 · similarity 0.88)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.88)
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.
