Content deleted Content added
Erel Segal (talk | contribs) |
m →Supermodular functions of subsets: removes unnecessary new line |
||
Line 28:
Let ''S'' be a finite set. A function <math>f\colon 2^S \to R</math> is supermodular if for any <math>A \subset B \subset S</math> and <math>x \in S \setminus B</math>, <math>f(A \cup \{x\})-f(A) \leq f(B \cup \{x\})-f(B)</math>. For submodularity, the inequality is reversed.
<!--
A simple illustrative example motivates this definition of submodular. Let S be a set of different foods, <math>M \subset S</math> a meal, and <math>f(M)</math> the "goodness" of that meal. Then A above is one meal, and B is A but with even more options. Let x be ice cream. Adding ice cream to a meal is always good, but it is best if there is not already a dessert. If A and B either both have a dessert or both do not, then adding ice cream to them is comparably good. But if A does not have dessert and B does, then the effect of adding ice cream is more pronounced in A.
| |||