1
$\begingroup$

Say we had 3 submodular functions $f(X)$, $g(X)$ and $h(X)$ is $\frac{f(X)}{g(X). h(X)}$ submodular as well? What can be said about the submodularity of $\frac{f(X)}{g(X)}$ and $f(X).g(X)$? I understand that the linear combinations of submodular functions are submodular, but what about the above cases? How can we prove or disprove them?

$\endgroup$
1
$\begingroup$

Here is a counterexample. Let $f(x)=\sqrt{x}$. This is submodular. Consider $g(x)=x$. This is linear/submodular. $\frac{f(x)}{g(x)}=x^{-0.5}$ which is not submodular.

In general, only nonnegative linear combinations of submodular functions are submodular. It is not preserved under division or multiplication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.