Submodular set function: Difference between revisions

Revision as of 09:49, 25 April 2019

Revision as of 23:32, 17 May 2019

Line 40:

=== Lovász extension ===

This extension is named after mathematician [[László Lovász]]. Consider any vector <math>\mathbf{x}=\{x_1,x_2,\dots,x_n\}</math> such that each <math>0\leq x_i\leq 1</math>. Then the Lovász extension is defined as <math>f^L(\mathbf{x})=\mathbb{E}(f(\{i|x_i\leqgeq \lambda\}))</math> where the expectation is over <math>\lambda</math> chosen from the [[uniform distribution (continuous)|uniform distribution]] on the interval <math>[0,1]</math>. The Lovász extension is a convex function.

=== Multilinear extension ===