Submodular set function: Difference between revisions

Revision as of 12:52, 8 July 2012

Revision as of 09:43, 17 July 2012

Line 45:

==Continuous extensions==

===Lovasz extension===

This extension has been named after [[László Lovász]]. Consider any vector <math>\bold{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the lovaszLovasz extension is defined as <math>f^L(\bold{x})=\mathbb{E}(f(\{i|x_i\geq \lambda\}))</math> where the expectation is over choosing <math>\lambda</math> uniformly in <math>[0,1]</math>. It can be shown that Lovasz extension is a convex function.

===Multilinear extension===

Consider any vector <math>\bold{x}=\{x_1,x_2,\ldots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the multilinear extension is defined as <math>F(\bold{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>