Research map / Learning theory and algorithms / Submodular and game algorithms
Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams
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 |
|---|---|---|---|
| Use adaptive thresholding instead of Sieve-Streaming's thresholding | Salsa · Maximum coverage in graphs, exemplar-based clustering, and movie recommendation | utility: around 10% | Helped |
| Use Salsa rather than Sieve-Streaming | Salsa · CIFAR-10 exemplar-based clustering | utility: around 5% higher utility | Helped |
| Use Salsa rather than Sieve-Streaming | Salsa · Spambase exemplar-based clustering | utility | Helped |
| Use Salsa or Two-Pass rather than Sieve-Streaming | Salsa and Two-Pass · Personalized movie recommendation, MovieLens 1M | gap to Greedy: around 40% of the gap | Helped |
| Use two passes with a lower threshold on the second pass | Two-Pass · Monotone submodular maximization | approximation ratio: 5/9 | Helped |
| Use a random-order stream rather than relying on arbitrary order | Salsa · Monotone submodular maximization | approximation ratio: 0.5 to a constant α > 0.5 | Helped |
Closest papers by meaning
- Do Less, Get More: Streaming Submodular Maximization with Subsampling (NeurIPS 2018 · similarity 0.91)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.89)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.89)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.89)
- Streaming Stochastic Submodular Maximization with On-Demand User Requests (NeurIPS 2025 · similarity 0.88)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · 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.