# Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint

arXiv: https://arxiv.org/abs/1607.04527 · HTML: https://mlsanity.com/paper/1607.04527/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2016.

## Built on by (most cited first, 1 of 1)

- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)

## Abstract (arXiv)

We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show that, for any fixed ε > 0, there exists a polynomial-time algorithm with an approximation ratio 1-c/e-ε, where c ∈ [0,1] is the (total) curvature of the input function. This approximation ratio is tight up to ε for any c ∈ [0,1]. To the best of our knowledge, this is the first result for a knapsack constraint that incorporates the curvature to obtain an approximation ratio better than 1-1/e, which is tight for general submodular functions. As an application of our result, we present a polynomial-time algorithm for the budget allocation problem with an improved approximation ratio.