Submodular set function: Difference between revisions

Revision as of 21:22, 25 October 2011

Revision as of 04:00, 1 November 2011

Line 10:

A submodular function is also a [[subadditive]] function, but a subadditive function need not be submodular.

==Applications==

==Types==

Line 50 ⟶ 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 convex 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==

===Operations which preserve Submodularity===

# Non-negative linear combinations. 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 <math>g(S)=\sum_{i=1}^k \alpha_i f_i(S)</math> is a submodular function.

# Consider any monotone submodular function <math>f</math> and a non negative number <math>c</math>. Then <math>g(S)=min(f(S),c)</math> is also a submodular function.

# Consider any submodular function <math>f</math>. Then <math>g(S)=f(\Omega-S)</math> is also a submodular function.

==Optimization problems==