Subadditive set function

Definition

Let Ω be a set and f : 2 Ω → R be a set function, where 2 Ω denotes the power set of Ω . The function f is subadditive if for each subset S and T of Ω , we have f ( S ) + f ( T ) ≥ f ( S ∪ T ) .

Examples of subadditive functions

Every non-negative submodular set function is subadditive (the family of 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 ⊆ Ω such that ∪ i = 1 m T i = Ω . Define f as the minimum number of subsets required to cover a given set. Formally, f ( S ) is the minimum number t such that there are sets T i 1 , … , T i t satisfying S ⊆ ∪ j = 1 t T i j . Then 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 } , let a i : Ω → R + be additive set functions. Then f ( S ) = max i ( ∑ x ∈ S a i ( x ) ) 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 is furthermore fractionally subadditive if it satisfies the following definition. For every S ⊆ Ω , every X 1 , … , X n ⊆ Ω , and every α 1 , … , α n ∈ [ 0 , 1 ] , if 1 S ≤ ∑ i = 1 n α i 1 X i , then f ( S ) ≤ ∑ i = 1 n α 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.