Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly beta about 0.42944
cs.DS, cs.DM
Submitted: 2026-11-10
Updated: 2026-11-10
Terminology
Sources
- A Refined Analysis of Submodular Greedy
- Practical Budgeted Submodular Maximization
- A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks
- Revisiting Modified Greedy Algorithm for Monotone Submodular Maximization with a Knapsack Constraint
- "Bring Your Own Greedy"+Max: Near-Optimal $1/2$-Approximations for Submodular Knapsack
- Data-dependent Evaluations for Budgeted Submodular Maximization
Related papers
- Exploiting Low Scanwidth to Resolve Soft Polytomies
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time