One motivation for the study of weak submodular functions is to bridge the gap between worst-case theory and the performance of algorithms practice. At the other extreme, one can consider the deviation of a submodular function from linearity. This leads to the notion of curvature which can be used to strengthen approximation bounds for both for general submodular functions [1]}, [2]}, [3]}, [4]}, [5]}, as well as in combination with weak submodularity [6]}. Inspired by insights from continuous optimization, Pokutta et al. [7]} have recently introduced a new notion of sharpness, which provides further explanation for the empirically good performance of the greedy algorithm on submodular objectives.
