Monotone decomposition of a submodular set function ($f=g+h$)

Every real-valued submodular set function on a finite ground set $V$ is the sum of a normalised set function $g$ that is nonnegative, monotone and submodular, and a modular set function $h$. A useful explicit choice isProof. The formula makes $h$ a modular set function, so $g$ is a submodular set function. It is a normalised set function because $h(\varnothing )=f(\varnothing )$. For $x\notin S$, diminishing returns gives ${\Delta }_{x}f(S)\ge {\Delta }_{x}f(V\setminus \{x\})=d_x$, hence ${\Delta }_{x}g(S)\ge 0$. Thus $g$ is a monotone set function, and starting at zero makes it a nonnegative function. The decomposition separates all potentially negative terminal marginal increments into the simple additive term. A constant term in $h$ is necessary unless $f$ is already a normalised set function.