  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. As an application of
our result, we present a polynomial-time algorithm for the budget allocation
problem with an improved approximation ratio.
