Content deleted Content added
created the basic page |
m improved bracketing |
||
Line 11:
# Fractionally subadditive set function. This is a generalization of submodular function and special case of subadditive function. If <math>\Omega</math> is a [[set (mathematics)|set]], a fractionally subadditive function is a set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, where <math>2^\Omega</math> denotes the [[Power set#Representing subsets as functions|power set]] of <math>\Omega</math>, which satisfies one of the following equivalent definitions<ref name="UF" />.
## For every <math>S,X_1,X_2,\ldots,X_n\subseteq \Omega</math> such that <math>1_S\leq \sum_{i=1}^n \alpha_i 1_{S_i}</math> then we have that <math>f(S)\leq \sum_{i=1}^n \alpha_i f(S_i)</math>
## Let for each <math>i\in \{1,2,\ldots,m\}, a_i:\Omega\rightarrow \mathbb{R}_+</math> be linear set functions. Then <math>f(S)=\max_{i}\left(\sum_{x\in S}a_i(x)\right)</math>
== See also ==
| |||