Submodular set function: Difference between revisions

Revision as of 03:30, 26 April 2012

Revision as of 13:13, 7 May 2012

Line 52:

===Concave Closure===

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 convexconcave closure is defined as <math>f^+(\bold{x})=\max(\sum_S \alpha_S f(S):\sum_S \alpha_S 1_S=\bold{x},\sum_S \alpha_S=1,\alpha_S\geq 0)</math>.

==Properties==