Research map / Learning theory and algorithms / Submodular and game algorithms
Optimal Sampling Gaps for Adaptive Submodular Maximization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 |
|---|---|---|---|
| Sample each item with probability at least r | Optimal policywise submodular maximization over independence systems · Independence systems | sampling gap: 1/r | Mixed |
| Use sampling rate 0.6 rather than the full dataset | Adaptive greedy (AG) · Adaptive viral marketing: Wikivote, NetHEPT, NetPHY, Epinions | influence spread: within 10% | Hurt |
| Use sampling rate 0.1 rather than the full dataset | Adaptive greedy (AG) · Adaptive viral marketing: NetHEPT, NetPHY, Epinions | influence spread | Helped |
| Use adaptive greedy rather than non-adaptive greedy | Viral marketing algorithms · Adaptive viral marketing | influence spread | Helped |
| Use random selection rather than adaptive greedy | Viral marketing algorithms · Adaptive viral marketing | influence spread | Hurt |
| Use sampling rate at least 0.3 rather than the full pool | Adaptive greedy (AG) · Pool-based active learning | version space reduction: within 10% | Hurt |
| Use sampling rate at least 0.5 rather than the full pool | Adaptive greedy (AG) · Pool-based active learning | version space reduction: within 5% | Hurt |
| Use adaptive greedy rather than non-adaptive greedy or random selection | Active learning query selection · Pool-based active learning | version space reduction | Helped |
Closest papers by meaning
- Approximation Guarantees for Adaptive Sampling (ICML 2018 · similarity 0.91)
- Do Less, Get More: Streaming Submodular Maximization with Subsampling (NeurIPS 2018 · similarity 0.89)
- Beyond Adaptive Submodularity: Approximation Guarantees of Greedy Policy with Adaptive Submodularity Ratio (ICML 2019 · similarity 0.89)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.87)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.87)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.87)
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.