= Monotone decomposition of a submodular set function
{title2=$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 is
$$
d_x=f(V)-f(V\setminus\{x\}),\qquad
h(S)=f(\varnothing)+\sum_{x\in S}d_x,\qquad g=f-h.
$$
\b[Proof.] 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)\geq\Delta_x f(V\setminus\{x\})=d_x$, hence $\Delta_xg(S)\geq0$. 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>.
Back to article page
