A Primal-Dual Analysis of Monotone Submodular Maximization

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.