Submodular set function: Difference between revisions

Revision as of 13:38, 5 October 2011

Revision as of 13:38, 5 October 2011

Line 30:

===Lovasz extension===

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 lovasz 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>.

===Multilinear Extensionextension===

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) \Pi_prod_{i\in S} x_i \Pi_prod_{i\notin S} (1-x_i)</math>

==Optimization problems==