Content deleted Content added
→Definition: cleans formal definition |
→Properties: This section was misleading. It stated a property of submodular functions, not subadditive ones. Tag: section blanking |
||
Line 13:
Fractionally subadditive set functions are a generalization of submodular functions and a special case of subadditive functions. A subadditive function <math>f</math> is furthermore fractionally subadditive if it satisfies the following definition.<ref name="UF" /> For every <math>S \subseteq \Omega</math>, every <math>X_1, \dotsc, X_n \subseteq \Omega</math>, and every <math>\alpha_1, \dotsc, \alpha_n \in [0, 1]</math>, if <math>1_S \leq \sum_{i=1}^n \alpha_i 1_{X_i}</math>, then <math>f(S) \leq \sum_{i=1}^n \alpha_i f(X_i)</math>. The set of fractionally subadditive functions equals the set of functions that can be expressed as the maximum of additive functions, as in the example in the previous paragraph.<ref name="UF" />
== See also ==
| |||