  We present an optimal, combinatorial 1-1/e approximation algorithm for
monotone submodular optimization over a matroid constraint. Compared to the
continuous greedy algorithm (Calinescu, Chekuri, Pal and Vondrak, 2008), our
algorithm is extremely simple and requires no rounding. It consists of the
greedy algorithm followed by local search. Both phases are run not on the
actual objective function, but on a related non-oblivious potential function,
which is also monotone submodular. Our algorithm runs in randomized time
O(n^8u), where n is the rank of the given matroid and u is the size of its
ground set. We additionally obtain a 1-1/e-eps approximation algorithm running
in randomized time O (eps^-3n^4u). For matroids in which n = o(u), this
improves on the runtime of the continuous greedy algorithm. The improvement is
due primarily to the time required by the pipage rounding phase, which we avoid
altogether. Furthermore, the independence of our algorithm from pipage rounding
techniques suggests that our general approach may be helpful in contexts such
as monotone submodular maximization subject to multiple matroid constraints.
  Our approach generalizes to the case where the monotone submodular function
has restricted curvature. For any curvature c, we adapt our algorithm to
produce a (1-e^-c)/c approximation. This result complements results of Vondrak
(2008), who has shown that the continuous greedy algorithm produces a
(1-e^-c)/c approximation when the objective function has curvature c. He has
also proved that achieving any better approximation ratio is impossible in the
value oracle model.
