Optimal approximation for submodular and supermodular optimization with bounded curvature

Understand

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint.

• Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature $c$.
• In the case of submodular maximization with curvature $c$, we obtain a $(1-c/e)$-approximation --- the first improvement over the greedy $(1-e^{-c})/c$-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint.
• Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function.