Research map / Learning theory and algorithms / Submodular and game algorithms
Instance Specific Approximations for 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 |
|---|---|---|---|
| Use Dual to bound greedy's instance-specific approximation | Greedy · Wide variety of real-world datasets and objectives | approximation: almost always over 0.85; often exceeds 0.95 | Helped |
| Use Dual rather than Top-k, Marginal, or Curvature to estimate greedy's approximation | Greedy · Large instances | approximation bound | Helped |
| Use Dual rather than Marginal to estimate greedy's approximation | Greedy · Large instances | approximation bound | Helped |
| Use Integer Program rather than Dual to estimate greedy's approximation | Greedy on coverage objectives · Youtube and Uber | approximation: above 0.99; between 0.95 and 0.98 | Helped |
| Use Dual rather than the other benchmarks | Greedy · Small instances, MovieLens facility location | approximation bound | Helped |
| Use Dual rather than Marginal, Curvature, or Sharpness | Greedy · Small instances, MovieLens movie recommendation | approximation bound | Mixed |
| Use partitioning instead of the additive lower bound on the dual objective (ablation) | Dual coverage-function method · Coverage objective | approximation: a small improvement | Helped |
| Apply the upper-bound method to marginal functions for sets in the collection (ablation) | Dual · MovieLens | approximation: minor | Helped |
| Apply the upper-bound method to marginal functions for sets in the collection (ablation) | Dual · YouTube | approximation: around 0.1 | Helped |
| Use Lazier-than-lazy greedy instead of Greedy | Submodular maximization algorithm · Real-world datasets and objectives | approximation: 0.02 to 0.05 worse | Mixed |
| Use Random greedy instead of Greedy | Submodular maximization algorithm · Real-world datasets and objectives | approximation | Hurt |
| Use Curvature or Sharpness rather than Dual for the approximation estimate | Greedy · MovieLens facility location, n = 2k, k=10 | runtime (seconds): 0.0246 vs 74.7; 0.0246 vs 187 | Hurt |
Closest papers by meaning
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.92)
- Robust Submodular Maximization: A Non-Uniform Partitioning Approach (ICML 2017 · similarity 0.92)
- Guarantees for Greedy Maximization of Non-submodular Functions with Applications (ICML 2017 · similarity 0.92)
- A Unified Approach to Submodular Maximization Under Noise (NeurIPS 2025 · similarity 0.92)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.91)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.90)
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.