Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 53:
=== Multilinear extension ===
Consider any vector <math>\mathbf{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 <ref>{{Cite journal |last=Vondrak |first=Jan |date=2008-05-17 |title=Optimal approximation for the submodular welfare problem in the value oracle model |url=https://doi.org/10.1145/1374376.1374389 |journal=Proceedings of the fortieth annual ACM symposium on Theory of computing |series=STOC '08 |___location=New York, NY, USA |publisher=Association for Computing Machinery |pages=67–74 |doi=10.1145/1374376.1374389 |isbn=978-1-60558-047-0}}</ref><ref>{{Cite journal |last=Calinescu |first=Gruia |last2=Chekuri |first2=Chandra |last3=Pál |first3=Martin |last4=Vondrák |first4=Jan |date=2011-01 |title=Maximizing a Monotone Submodular Function Subject to a Matroid Constraint |url=http://epubs.siam.org/doi/10.1137/080733991 |journal=SIAM Journal on Computing |language=en |volume=40 |issue=6 |pages=1740–1766 |doi=10.1137/080733991 |issn=0097-5397}}</ref><math>F(\mathbf{x})=\sum_{S\subseteq \Omega} f(S) \prod_{i\in S} x_i \prod_{i\notin S} (1-x_i)</math>.
Intuitively, ''x<sub>i</sub>'' represents the probability that item ''i'' is chosen for the set. For every set ''S'', the two inner products represent the probability that the chosen set is exactly ''S''. Therefore, the sum represents the expected value of ''f'' for the set formed by choosing each item ''i'' at random with probability xi, independently of the other items.
| |||