  In this paper we design a new primal-dual algorithm for the classic discrete
optimization problem of maximizing a monotone submodular function subject to a
cardinality constraint achieving the optimal approximation of $(1-1/e)$. This
problem and its special case, the maximum $k$-coverage problem, have a wide
range of applications in various fields including operations research, machine
learning, and economics. While greedy algorithms have been known to achieve
this approximation factor, our algorithms also provide a dual certificate which
upper bounds the optimum value of any instance. This certificate may be used in
practice to certify much stronger guarantees than the worst-case $(1-1/e)$
approximation factor.
