Subadditive set function: Difference between revisions

Revision as of 19:21, 14 July 2015

Latest revision as of 19:41, 19 February 2025

(14 intermediate revisions by 9 users not shown)

Line 2:

== 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]].]]

Every non-negative [[submodular set function]] is subadditive (the family of non-negative submodular functions is strictly contained in the family of subadditive functions).

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.

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

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 ''f'' is a submodular set function and ''T'' is a subset of ''&Omega;'' in which each element of ''&Omega;'' is included in ''T'' with probability ''p'', then the [[expected value]] of ''f''(''T'') is at least ''pf''(''&Omega;'').

== See also ==

Line 26 ⟶ 23:

{{reflist|

refs=

<ref name="UF">{{cite articlejournal | first=Uriel | last=Feige | authorlink=Uriel Feige | title=On Maximizing Welfare when Utility Functions are Subadditive | journal=SIAM Journal on Computing | volume=39 | issue=1 | year=2009 | pages=122–142 | doi=10.1137/070680977}}</ref>

<ref name="DNS">{{cite articlejournal | first1=Shahar | last1=Dobzinski | first2=Noam | last2=Nisan | first3=Michael | last3=Schapira | authorlink2=Noam Nisan | title=Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders | journal=[[Mathematics of Operations Research]] | volume=35 | issue=1 | year=2010 | 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| ]]