Submodular set function: Difference between revisions

Revision as of 06:03, 16 October 2013

Revision as of 17:26, 24 November 2013

Line 49:

# 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. Furthermore, 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 monotonic.

# If <math>f:2^\Omega\rightarrow \mathbb{R}_+</math> is a submodular function then <math>g:2^\Omega\rightarrow \mathbb{R}_+</math> defined as <math>g(S)=\phi(f(S))</math> where <math>\phi</math> is a [[concave]] function, is also a submodular function.

# 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(\phivarnothing)</math> where <math>\phivarnothing</math> is the null 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>.

== Optimization problems ==