Submodular set function: Difference between revisions

Revision as of 01:08, 3 October 2011

Revision as of 01:16, 3 October 2011

Line 1:

{{Userspace draft|source=ArticleWizard|date=October 2011}} <!-- Please leave this line alone! -->

'''Submodular functions''' are set functions which usually appear in approximation algorithms, functions modeling user preferences in game theory. These functions have a natural diminishing returns property which makes them suitable for many applications.

==Definition==

'''Submodular function''' is a set function <math>f:2^{\Omega}\rightarrow R</math> such that for any <math>X\subseteq Y\subseteq \Omega</math> and <math>x\in \Omega\backslash Y</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>. A submodular function is also a [[subadditive]] function, but a subadditive function need not be submodular.

and <math>x\in \Omega\backslash Y</math> we have that <math>f(X\cup \{x\})-f(X)\geq f(Y\cup \{x\})-f(Y)</math>

==Examples==