2
$\begingroup$

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

$\endgroup$
  • 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$ – Chandra Chekuri Feb 26 '18 at 4:30

Your Answer

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

Browse other questions tagged or ask your own question.