Subadditive set function: Difference between revisions

Revision as of 09:04, 1 May 2015

Revision as of 09:05, 1 May 2015

Line 13:

{{space|10}} <math>f(S)=\min t</math> such that there exists sets <math>T_{i_1},T_{i_2},\dots,T_{i_t}</math> satisfying <math>S\subseteq \cup_{j=1}^t T_{i_j}</math>.

3. The [[maximum]] of [[additive map|additive set function]]s is subadditive (Dually, the [[minimum]] of additive functions is [[superadditive set function|superadditive]]). Formally, let for each <math>i\in \{1,2,\ldots,m\}, a_i:\Omega\rightarrow \mathbb{R}_+</math> be linear (additive) set functions. Then <math>f(S)=\max_{i}\left(\sum_{x\in S}a_i(x)\right)</math> is a subadditive set function.

4. '''Fractionally subadditive set functions'''. 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 the following definition:<ref name="UF" />