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$ Feb 26, 2018 at 4:30


Your Answer

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

Browse other questions tagged or ask your own question.