  We design new approximation algorithms for the problems of optimizing
submodular and supermodular functions subject to a single matroid constraint.
Specifically, we consider the case in which we wish to maximize a nondecreasing
submodular function or minimize a nonincreasing supermodular function in the
setting of bounded total curvature $c$. In the case of submodular maximization
with curvature $c$, we obtain a $(1-c/e)$-approximation --- the first
improvement over the greedy $(1-e^{-c})/c$-approximation of Conforti and
Cornuejols from 1984, which holds for a cardinality constraint, as well as
recent approaches that hold for an arbitrary matroid constraint.
  Our approach is based on modifications of the continuous greedy algorithm and
non-oblivious local search, and allows us to approximately maximize the sum of
a nonnegative, nondecreasing submodular function and a (possibly negative)
linear function. We show how to reduce both submodular maximization and
supermodular minimization to this general problem when the objective function
has bounded total curvature. We prove that the approximation results we obtain
are the best possible in the value oracle model, even in the case of a
cardinality constraint.
  We define an extension of the notion of curvature to general monotone set
functions and show $(1-c)$-approximation for maximization and
$1/(1-c)$-approximation for minimization cases. Finally, we give two concrete
applications of our results in the settings of maximum entropy sampling, and
the column-subset selection problem.
