Research map / Learning theory and algorithms / Submodular and game algorithms
Regularized Submodular Maximization at Scale
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 AlgStream instead of greedy or sieve-streaming | regularized submodular maximization for directed vertex cover · four real-world networks | objective value | Helped |
| Use AlgStream instead of distorted greedy | regularized submodular maximization for directed vertex cover · four real-world networks | objective value | Hurt |
| Estimate β_OPT and choose r based on that estimate | AlgStream for SLC mode finding · mode finding of SLC distributions | objective value | Helped |
| Use AlgStream instead of distorted greedy | SLC mode finding · cardinality constraints larger than k=20 | objective value | Helped |
| Use AlgDistributed instead of distributed greedy | distributed regularized optimization · Amazon, DBLP, Youtube, and Pokec graphs | objective value | Helped |
| Directly maximize the regularized objective instead of maximizing g with a knapsack constraint on ℓ | video summarization · VSUMM videos 13 and 15 | objective value | Helped |
| Increase the entropy penalty weight λ (ablation) | AlgStream for video summarization · video 14, k=6 | entropy of selected frames: λ ∈ {0,0.5, 1.0} | Helped |
| Increase the entropy penalty weight λ (ablation) | AlgStream for video summarization · video 14, k=6 | representativeness: λ ∈ {0,0.5, 1.0} | Hurt |
| Directly maximize the regularized objective instead of maximizing g subject to a knapsack constraint | movie recommendation · varying cardinality constraint | objective value | No clear effect |
| Use AlgStream instead of sieve-streaming | movie recommendation · varying cardinality constraint | utility | Helped |
| Use AlgStream instead of sieve-streaming or Greedy Dynamic Program | Twitter text summarization · varying cardinality constraint and linear-cost choices | objective value | Helped |
| Use AlgStream instead of the strongest offline algorithms | Twitter text summarization · varying cardinality constraint and linear-cost choices | objective value | Hurt |
Closest papers by meaning
- Streaming Submodular Maximization under a k-Set System Constraint (ICML 2020 · similarity 0.91)
- Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (ICML 2019 · similarity 0.91)
- Cardinality constrained submodular maximization for random streams (NeurIPS 2021 · similarity 0.91)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.90)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.90)
- Consistent Submodular Maximization (ICML 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.