Subadditive set function

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

If ${\displaystyle \Omega }$  is a set, a subadditive function is a set function ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$ , where ${\displaystyle 2^{\Omega }}$  denotes the power set of ${\displaystyle \Omega }$ , which satisfies one of the following equivalent definitions.

1. For every ${\displaystyle S,T\subseteq \Omega }$  we have that ${\displaystyle f(S)+f(T)\geq f(S\cup T)}$ .

Examples of subadditive functions

1. Submodular set function
2. Fractionally subadditive set function. This is a generalization of submodular function and special case of subadditive function. If ${\displaystyle \Omega }$  is a set, a fractionally subadditive function is a set function ${\displaystyle f:2^{\Omega }\rightarrow \mathbb {R} }$ , where ${\displaystyle 2^{\Omega }}$  denotes the power set of ${\displaystyle \Omega }$ , which satisfies one of the following equivalent definitions^[1].
   1. For every ${\displaystyle S,X_{1},X_{2},\ldots ,X_{n}\subseteq \Omega }$  such that ${\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{S_{i}}}$  then we have that ${\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(S_{i})}$ 
   2. Let for each ${\displaystyle i\in \{1,2,\ldots ,m\},a_{i}:\Omega \rightarrow \mathbb {R} _{+}}$  be linear set functions. Then ${\displaystyle f(S)=\max _{i}(\sum _{x\in S}a_{i}(x))}$ 

See also

• Submodular set function

Citations

1. U. Feige, On Maximizing Welfare when Utility Functions are Subadditive, SIAM J. Comput 39 (2009), pp. 122-142.