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

Understand

We consider the problem of maximizing a monotone submodular function under a knapsack constraint.

• We show that, for any fixed $\epsilon > 0$, there exists a polynomial-time algorithm with an approximation ratio $1-c/e-\epsilon$, where $c \in [0,1]$ is the (total) curvature of the input function.
• This approximation ratio is tight up to $\epsilon$ for any $c \in [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.