|
== Definition ==
IfLet <math>\Omega</math> isbe a [[set (mathematics)|set]], a subadditive function is a set functionand <math>f: \colon 2^{\Omega} \rightarrow \mathbb{R}</math> be a [[set function]], where <math>2^\Omega</math> denotes the [[Power set#Representing subsets as functions|power set]] of <math>\Omega</math>. The function ''f'' is ''subadditive'' if for each subset <math>S</math> and <math>T</math> of <math>\Omega</math>, whichwe satisfieshave the<math>f(S) following+ inequalityf(T) \geq f(S \cup T)</math>.<ref name="UF" /><ref name="DNS" /> Note that by substitution of <math>T=S</math> into the defining equation, it follows that <math>f(S) \ge 0</math> for all {{tmath|S}}.
For every <math>S, T \subseteq \Omega</math> we have that <math>f(S)+f(T)\geq f(S\cup T)</math>.
== Examples of subadditive functions ==
[[Image:Principle of sigma-subadditivity.svg|thumb|Everyday example of sigma sub-additivity: when sand is mixed with water, the [[bulk volume]] of the mixture is smaller than the sum of the individual volumes, as the water can lodge in the spaces between the sand grains. A similar situation with a different mechanism occurs when ethanol is mixed with water, see [[apparent molar property]].]]
1. Every non-negative [[submodular set function]] is subadditive (the family of submodular functions is strictly contained in the family of subadditive functions). ▼
▲1. Every non-negative [[submodular set function]] is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions).
2. 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 the minimum number of subsets required to cover a given set:
{{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>.
The function that counts the number of sets required to [[set cover|cover]] a given set is subadditive. Let <math>T_1, \dotsc, T_m \subseteq \Omega</math> such that <math>\cup_{i=1}^m T_i=\Omega</math>. Define <math>f</math> as the minimum number of subsets required to cover a given set. Formally, <math>f(S)</math> is the minimum number <math>t</math> such that there are sets <math>T_{i_1}, \dotsc, T_{i_t}</math> satisfying <math>S\subseteq \cup_{j=1}^t T_{i_j}</math>. Then <math>f</math> is subadditive.
3. The [[maximum]] of [[additive map|additive set function]]s is subadditive (Dually, the [[minimum]] of additive functions is [[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. ▼
▲3. The [[maximum]] of [[additive map|additive set function]]s is subadditive ( Duallydually, the [[minimum]] of additive functions is [[superadditive]]). Formally, let for each <math>i \in \{1, 2, \ ldotsdotsc, m\} </math>, let <math>a_i : \colon \Omega \ rightarrowto \mathbb{R} _+</math> be linear (additive ) set functions. Then <math>f(S)=\max_{i} \left(\sum_{x\in S}a_i( x)\rightS)</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" />
* 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_{X_i}</math> then we have that <math>f(S)\leq \sum_{i=1}^n \alpha_i f(X_i)</math>.
* This definition is equivalent to the definition of the maximum in 3 above.<ref name="UF" />
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" />
== Properties ==
# If <math>T</math> is a set chosen such that each <math>e\in \Omega</math> is included into <math>T</math> with probability <math>p</math> then the following inequality is satisfied <math>\mathbb{E}[f(T)]\geq p f(\Omega)</math>.
== See also ==
* [[Submodular set function]]
* [[Utility functions on indivisible goods]]
== Citations ==
{{reflist|
refs=
<ref name="UF">[[{{cite journal | first=Uriel | last=Feige |U. authorlink=Uriel Feige]], | title=On Maximizing Welfare when Utility Functions are Subadditive, | journal=SIAM J.Journal Computon Computing | volume=39 (| issue=1 | year=2009), pp.| pages=122–142 | doi=10.1137/070680977}}</ref>
<ref name="DNS">S.{{cite journal | first1=Shahar | last1=Dobzinski, [[| first2=Noam Nisan|N. last2=Nisan]],M. | first3=Michael | last3=Schapira, | authorlink2=Noam Nisan | title=Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders, Math.| Oper.journal=[[Mathematics Res.of Operations Research]] | volume=35 (| issue=1 | year=2010), pp.| pages=1–13 | doi=10.1145/1060590.1060681| s2cid=2685385 | citeseerx=10.1.1.79.6803 }}</ref>
}}
<!--- Categories --->
[[:Category:Combinatorial optimization| ]]
[[:Category:Approximation algorithms| ]] ▼
[[Category:Combinatorial optimization]]
▲[[ :Category:Approximation algorithms | ]]
| 