Content deleted Content added
link U. Feige |
link L. Lovasz |
||
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 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>. 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>
Line 81:
{{reflist|
refs=
<ref name="GLS">M. Grotschel, [[László Lovász|L. Lovasz]], and [[Alexander Schrijver|A. Schrijver]], The ellipsoid method and its consequences in combinatorial optimization,Combinatorica,1 (1981),pp. 169–197.</ref>
<ref name="Cunningham">W. H. Cunningham, On submodular function minimization, Combinatorica,5 (1985),pp. 185–192.</ref>
<ref name="IFF"> S. Iwata, L. Fleischer, and S. Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions,J. ACM,48 (2001),pp. 761–777</ref>
| |||