AI Paper Atlas

Research map / Learning theory and algorithms / Submodular and game algorithms

Submodular + Concave

Siddharth Mitra, Moran Feldman, amin karbasi

NeurIPS 2021 · Learning theory and algorithms › Submodular and game algorithms · approach: Monotone submodular maximization · 0 citations (OpenAlex)

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 changedWhereMeasuredEffect
Use Greedy Frank-Wolfe for monotone non-negative G and CDR-submodular + concave maximization over a general solvable convex body · General convex body Papproximation coefficient for G and C: 1-1/eImproved
Use Measured Greedy Frank-Wolfe when P is down-closed and both functions are non-negativeDR-submodular + concave maximization · Down-closed Papproximation coefficient for non-monotone components: e^{-1}Improved
Combine the gradients of G and C and initialize near a maximizer of CGradient Combining Frank-Wolfe · General convex body P; monotone non-negative Gapproximation coefficient for C: 1Improved
Use a non-oblivious auxiliary objective for GNon-Oblivious Frank-Wolfe · General convex body P; monotone non-negative G and non-negative Capproximation coefficient for G: 1 - 1/e - 4ε ln ε^{-1}Improved
Use a non-oblivious auxiliary objective for GNon-Oblivious Frank-Wolfe · General convex body P; monotone non-negative G and non-negative Capproximation coefficient for C: 1 - 4ε ln ε^{-1}Improved
Apply the proposed algorithms rather than natural baselinesDR-submodular + concave objectives · Quadratic programming and other tested objectivesobjective valueImproved

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy