Research map / Learning theory and algorithms / Submodular and game algorithms
Submodular + Concave
Siddharth Mitra, Moran Feldman, amin karbasi
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 Greedy Frank-Wolfe for monotone non-negative G and C | DR-submodular + concave maximization over a general solvable convex body · General convex body P | approximation coefficient for G and C: 1-1/e | Improved |
| Use Measured Greedy Frank-Wolfe when P is down-closed and both functions are non-negative | DR-submodular + concave maximization · Down-closed P | approximation coefficient for non-monotone components: e^{-1} | Improved |
| Combine the gradients of G and C and initialize near a maximizer of C | Gradient Combining Frank-Wolfe · General convex body P; monotone non-negative G | approximation coefficient for C: 1 | Improved |
| Use a non-oblivious auxiliary objective for G | Non-Oblivious Frank-Wolfe · General convex body P; monotone non-negative G and non-negative C | approximation coefficient for G: 1 - 1/e - 4ε ln ε^{-1} | Improved |
| Use a non-oblivious auxiliary objective for G | Non-Oblivious Frank-Wolfe · General convex body P; monotone non-negative G and non-negative C | approximation coefficient for C: 1 - 4ε ln ε^{-1} | Improved |
| Apply the proposed algorithms rather than natural baselines | DR-submodular + concave objectives · Quadratic programming and other tested objectives | objective value | Improved |
Closest papers by meaning
- Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions (NeurIPS 2018 · similarity 0.91)
- Continuous Submodular Maximization: Beyond DR-Submodularity (NeurIPS 2020 · similarity 0.91)
- Submodular Maximization beyond Non-negativity: Guarantees, Fast Algorithms, and Applications (ICML 2019 · similarity 0.90)
- From Linear to Linearizable Optimization: A Novel Framework with Applications to Stationary and Non-stationary DR-submodular Optimization (NeurIPS 2024 · similarity 0.88)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.88)
- Discrete and Continuous Difference of Submodular Minimization (ICML 2025 · 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.
