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

Let be a set and be a set function, where denotes the power set of. The function f is subadditive if for each subset and of, we have.

Examples of subadditive functions

Every non-negative submodular set function is subadditive.
The function that counts the number of sets required to cover a given set is subadditive. Let such that. Define as the minimum number of subsets required to cover a given set. Formally, is the minimum number such that there are sets satisfying. Then is subadditive.
The maximum of additive set functions is subadditive. Formally, for each, let be additive set functions. Then 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 is furthermore fractionally subadditive if it satisfies the following definition. For every, every, and every, if, then. 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.

Citations