Subadditive set function: Difference between revisions

Revision as of 13:56, 28 January 2013

Revision as of 14:49, 22 October 2013

Line 9:

# [[Submodular set function]]. Every non-negative submodular function is also a subadditive function.

# 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_iX_i}</math> then we have that <math>f(S)\leq \sum_{i=1}^n \alpha_i f(S_iX_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>

# Functions based on [[set cover]]. Let <math>T_1,T_2,\ldots,T_m\subseteq \Omega</math> such that <math>\cup_{i=1}^m T_i=\Omega</math>. Then <math>f</math> is defined as follows