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 the following inequality.^[1][2]

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. Every non-negative submodular set function is subadditive (the family of submodular functions is strictly contained in the family of subadditive functions).

2. Functions based on set cover. Let ${\displaystyle T_{1},T_{2},\ldots ,T_{m}\subseteq \Omega }$  such that ${\displaystyle \cup _{i=1}^{m}T_{i}=\Omega }$ . Then ${\displaystyle f}$  is defined as the minimum number of subsets required to cover a given set:            ${\displaystyle f(S)=\min t}$  such that there exists sets ${\displaystyle T_{i_{1}},T_{i_{2}},\dots ,T_{i_{t}}}$  satisfying ${\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}}$ .

3. The maximum of additive set functions is subadditive (Dually, the minimum of additive functions is superadditive). Formally, let for each ${\displaystyle i\in \{1,2,\ldots ,m\},a_{i}:\Omega \rightarrow \mathbb {R} _{+}}$  be linear (additive) set functions. Then ${\displaystyle f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)}$  is a subadditive set function.

4. Fractionally subadditive set functions. 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 the following definition:^[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_{X_{i}}}$  then we have that ${\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})}$ .
• This definition is equivalent to the definition of the maximum in 3 above.^[1]

Properties

1. If ${\displaystyle T}$  is a set chosen such that each ${\displaystyle e\in \Omega }$  is included into ${\displaystyle T}$  with probability ${\displaystyle p}$  then the following inequality is satisfied ${\displaystyle \mathbb {E} [f(T)]\geq pf(\Omega )}$ .

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.
2. S. Dobzinski, N. Nisan,M. Schapira, Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders, Math. Oper. Res. 35 (2010), pp. 1–13.