Research map / Learning theory and algorithms / Submodular and game algorithms
Submodular Maximization Through Barrier Functions
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 barrier-function local search for constrained submodular maximization | AlgBarrier · Vertex cover on Facebook ego and EU Email exchange networks | objective value | Helped |
| Use barrier-function local search instead of the compared baselines | Video summarization on VSUMM · Video summarization | utility: up to 50% more | Helped |
| Use the heuristic barrier variant that permits solutions with aggregate knapsack cost above 1 | AlgHeuristic · Yelp location summarization | objective value | Helped |
| Use the heuristic barrier variant that permits solutions with aggregate knapsack cost above 1 | AlgHeuristic · Twitter text summarization with two knapsacks | objective value | Helped |
| Increase the number of knapsack constraints from one to two | Compared algorithms · Twitter text summarization | objective value | Hurt |
Closest papers by meaning
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.90)
- Non-monotone Sequential Submodular Maximization (AAAI 2024 · similarity 0.89)
- Deletion-Robust Submodular Maximization with Knapsack Constraints (AAAI 2024 · similarity 0.89)
- Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.89)
- Discretely beyond $1/e$: Guided Combinatorial Algortihms for Submodular Maximization (NeurIPS 2024 · similarity 0.89)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · 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.