# A Primal-Dual Analysis of Monotone Submodular Maximization

arXiv: https://arxiv.org/abs/2311.07808 · HTML: https://mlsanity.com/paper/2311.07808/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Nov 2023.

## Built on by (most cited first, 1 of 1)

- [Data-dependent Evaluations for Budgeted Submodular Maximization](https://mlsanity.com/paper/2607.05759/) (2026)

## Abstract (arXiv)

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.