What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?

  • 1
    $\begingroup$ Symmetric submodular functions are essentially non-monotone. For any submodular function $f$ you can create a symmetric function $g$ by setting $g(S) = f(S) + f(N\setminus S) - f(N)$ where $N$ is the ground set. Also, if $f$ is a submodular and $w$ is a modular function then $f-w$ can be non-monotone even if $f$ is monotone. Think of $f$ as a utility function and $w$ as prices. $\endgroup$ Commented Feb 26, 2018 at 4:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.