Misplaced Pages

Subadditive set function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

Let Ω {\displaystyle \Omega } be a set and f : 2 Ω → R {\displaystyle f\colon 2^{\Omega }\rightarrow \mathbb {R} } be a set function, where 2 Ω {\displaystyle 2^{\Omega }} denotes the power set of Ω {\displaystyle \Omega } . The function f is subadditive if for each subset S {\displaystyle S} and T {\displaystyle T} of Ω {\displaystyle \Omega } , we have f ( S ) + f ( T ) ≥ f ( S ∪ T ) {\displaystyle f(S)+f(T)\geq f(S\cup T)} .

Examples of subadditive functions

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 cover a given set is subadditive. Let T 1 , … , T m ⊆ Ω {\displaystyle T_{1},\dotsc ,T_{m}\subseteq \Omega } such that ∪ i = 1 m T i = Ω {\displaystyle \cup _{i=1}^{m}T_{i}=\Omega } . Define f {\displaystyle f} as the minimum number of subsets required to cover a given set. Formally, f ( S ) {\displaystyle f(S)} is the minimum number t {\displaystyle t} such that there are sets T i 1 , … , T i t {\displaystyle T_{i_{1}},\dotsc ,T_{i_{t}}} satisfying S ⊆ ∪ j = 1 t T i j {\displaystyle S\subseteq \cup _{j=1}^{t}T_{i_{j}}} . Then f {\displaystyle f} is subadditive.

The maximum of additive set functions is subadditive (dually, the minimum of additive functions is superadditive). Formally, for each i ∈ { 1 , … , m } {\displaystyle i\in \{1,\dotsc ,m\}} , let a i : Ω → R + {\displaystyle a_{i}\colon \Omega \to \mathbb {R} _{+}} be additive set functions. Then f ( S ) = max i ( ∑ x ∈ S a i ( x ) ) {\displaystyle f(S)=\max _{i}\left(\sum _{x\in S}a_{i}(x)\right)} 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 f {\displaystyle f} is furthermore fractionally subadditive if it satisfies the following definition. For every S ⊆ Ω {\displaystyle S\subseteq \Omega } , every X 1 , … , X n ⊆ Ω {\displaystyle X_{1},\dotsc ,X_{n}\subseteq \Omega } , and every α 1 , … , α n ∈ [ 0 , 1 ] {\displaystyle \alpha _{1},\dotsc ,\alpha _{n}\in } , if 1 S ≤ ∑ i = 1 n α i 1 X i {\displaystyle 1_{S}\leq \sum _{i=1}^{n}\alpha _{i}1_{X_{i}}} , then f ( S ) ≤ ∑ i = 1 n α i f ( X i ) {\displaystyle f(S)\leq \sum _{i=1}^{n}\alpha _{i}f(X_{i})} . 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.

See also

Citations

  1. ^ Feige, Uriel (2009). "On Maximizing Welfare when Utility Functions are Subadditive". SIAM Journal on Computing. 39 (1): 122–142. doi:10.1137/070680977.
  2. Dobzinski, Shahar; Nisan, Noam; Schapira, Michael (2010). "Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders". Mathematics of Operations Research. 35 (1): 1–13. CiteSeerX 10.1.1.79.6803. doi:10.1145/1060590.1060681. S2CID 2685385.
Categories: