If $f$ is a submodular function, does $g(k) = \max_{|A| = k}f(A)$ have diminishing returns?

37 Views Asked by At

A submodular function has diminishing returns, so I expect the following: if $f$ is submodular, then $g(k) = \max_{A\subseteq \Omega, |A| = k}f (A)$ would also have diminishing returns, that is $g(k+1) - g(k) \leq g(k) - g(k-1)$.

Is this generally correct? If not, what if we require $f$ to be monotone and nonnegative?