# Subadditive set function

Jump to navigation
Jump to search

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 is a set, a subadditive function is a set function , where denotes the power set of , which satisfies the following inequality.^{[1]}^{[2]}

## Examples of subadditive functions

- Submodular set function. Every non-negative submodular function is also a subadditive function.
- Fractionally subadditive set function. This is a generalization of submodular function and special case of subadditive function. If is a set, a fractionally subadditive function is a set function , where denotes the power set of , which satisfies one of the following equivalent definitions.
^{[1]} - Functions based on set cover. Let such that . Then is defined as follows

Template:Space such that there exists sets satisfying

## Properties

- If is a set chosen such that each is included into with probability then the following inequality is satisfied