Content deleted Content added
Mathreader17 (talk | contribs) add a generic introduction to continuous extensions |
Mathreader17 (talk | contribs) add reference on Lovász extension |
||
Line 43:
=== Lovász extension ===
This extension is named after mathematician [[László Lovász]].<ref name="L" /> 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\geq \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 if and only if <math>f</math> is a submodular function.
=== Multilinear extension ===
Line 105:
<ref name="KG1">A. Krause and C. Guestrin, Near-optimal nonmyopic value of information in graphical models, UAI-2005.</ref>
<ref name="FNS">M. Feldman, J. Naor and R. Schwartz, A unified continuous greedy algorithm for submodular maximization, Proc. of 52nd FOCS (2011).</ref>
<ref name="L">{{cite journal |author-link1=László Lovász |last1=Lovász |first1=L. |date=1983 |title=Submodular functions and convexity |url= |journal=Mathematical Programming The State of the Art |pages=235-257 |doi=10.1007/978-3-642-68874-4_10 }}</ref>
}}
| |||