What are some interesting example of non-monotone submodular functions beside cut, directed cut in graphs?
$\begingroup$
$\endgroup$
1
-
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 ChekuriFeb 26, 2018 at 4:30
Add a comment
|