Subadditive set function: Difference between revisions

Revision as of 04:11, 3 January 2013

Revision as of 00:28, 17 January 2013

Line 8:

== 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 <math>\Omega</math> is a [[set (mathematics)|set]], a fractionally subadditive function is a set function <math>f:2^{\Omega}\rightarrow \mathbb{R}</math>, where <math>2^\Omega</math> denotes the [[Power set#Representing subsets as functions|power set]] of <math>\Omega</math>, which satisfies one of the following equivalent definitions.<ref name="UF" />.

## For every <math>S,X_1,X_2,\ldots,X_n\subseteq \Omega</math> such that <math>1_S\leq \sum_{i=1}^n \alpha_i 1_{S_i}</math> then we have that <math>f(S)\leq \sum_{i=1}^n \alpha_i f(S_i)</math>

## Let for each <math>i\in \{1,2,\ldots,m\}, a_i:\Omega\rightarrow \mathbb{R}_+</math> be linear set functions. Then <math>f(S)=\max_{i}\left(\sum_{x\in S}a_i(x)\right)</math>

Line 23:

{{reflist|

refs=

<ref name="UF"> [[Uriel Feige|U. Feige]], On Maximizing Welfare when Utility Functions are Subadditive, SIAM J. Comput 39 (2009), pp. 122–142.</ref>

<ref name="DNS"> S. Dobzinski,[[Noam Nisan|N. Nisan]],M. Schapira, Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders, Math. Oper. Res. 35 (2010), pp. 1–13.</ref>

}}

<!--- Categories --->