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.

论文设计了一种新的逼近算法来解决在单一拟阵约束下优化子模和超模函数的问题，特别地，当目标函数有闭合总曲率时，获得了一个 (1-c/e)- 近似的结果；该算法基于连续贪心算法和非随机局部搜索的修改，并进行了扩展以包括在一些特定场景下的应用，例如最大熵抽样和列子集选择问题。