Subadditive set function: Difference between revisions

Revision as of 02:25, 12 October 2014

Latest revision as of 19:41, 19 February 2025

(25 intermediate revisions by 11 users not shown)

Line 1:

In mathematics, a '''subadditive set function''' is a [[set function]] whose value, informally, has the property that the value of function on the union of two sets is at most the sum of values of the function on each of the sets. This is thematically related to the [[subadditivity]] property of real-valued functions.

== Definition ==

NEED EIGHT INCH Rock NOW

Let <math>\Omega</math> be a [[set (mathematics)|set]] and <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>, we have <math>f(S) + f(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}}.

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

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

{{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>.

== Properties ==

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

# 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>.

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} a_i(S)</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" />

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