Content deleted Content added
Line 54:
# The class of submodular functions is [[closure (mathematics)|closed]] under non-negative [[linear combination]]s. Consider any submodular function <math>f_1,f_2,\ldots,f_k</math> and non-negative numbers <math>\alpha_1,\alpha_2,\ldots,\alpha_k</math>. Then the function <math>g</math> defined by <math>g(S)=\sum_{i=1}^k \alpha_i f_i(S)</math> is submodular.
#For any submodular function <math>f</math>, the function defined by <math>g(S)=f(\Omega \setminus S)</math> is submodular.
#The function <math>g(S)=\min(f(S),c)</math>, where <math>c</math> is a real number, is submodular whenever <math>f</math> is monotone submodular. More generally, <math>g(S)=h(f(S))</math> is submodular, for any non decreasing concave function <math>h</math>.
# Consider a random process where a set <math>T</math> is chosen with each element in <math>\Omega</math> being included in <math>T</math> independently with probability <math>p</math>. Then the following inequality is true <math>\mathbb{E}[f(T)]\geq p f(\Omega)+(1-p) f(\varnothing)</math> where <math>\varnothing</math> is the empty set. More generally consider the following random process where a set <math>S</math> is constructed as follows. For each of <math>1\leq i\leq l, A_i\subseteq \Omega</math> construct <math>S_i</math> by including each element in <math>A_i</math> independently into <math>S_i</math> with probability <math>p_i</math>. Furthermore let <math>S=\cup_{i=1}^l S_i</math>. Then the following inequality is true <math>\mathbb{E}[f(S)]\geq \sum_{R\subseteq [l]} \Pi_{i\in R}p_i \Pi_{i\notin R}(1-p_i)f(\cup_{i\in R}A_i)</math>.{{Citation needed|date=November 2013}}
| |||