Subadditive set function: Difference between revisions

Revision as of 19:17, 19 February 2025

Latest revision as of 19:41, 19 February 2025

(3 intermediate revisions by the same user not shown)

Line 2:

== Definition ==

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" /> ByNote that by substitution of <math>T=S</math> into the defining equation, ifit follows that <math>f(S) \ge 0</math> for all {{tmath|S}}.

== Examples of subadditive functions ==

Line 12:

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" />