Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes

Chandra Chekuri, Jan Vondrák, Rico Zenklusen

We consider the problem of maximizing a non-negative submodular set function $f:2^N\to {\mathbb{R}}_{+}$ over a ground set $N$ subject to a variety of packing type constraints…