I am working on an optimization problem for my graduate research. I would like to know whether the square of the cardinality of a set is submodular or not.
Thank you in advance for the help.
Asked
Active
Viewed 43 times
1 Answers
1
No, $f(\{1,2\})+f(\emptyset) > f(\{1\})+f(\{2\})$.
In general, if $f(S)=g(|S|)$, then $f$ is supermodular if $g$ is concave and submodular if $g$ is convex.
p.s.
- 6,401
-
Thank you very much. That's a concise, simple example. – Jose Cadena Oct 29 '15 at 02:11