Optimal approximation for submodular and supermodular optimization with bounded curvature
Optimal approximation for submodular and supermodular optimization with bounded curvature
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 …