Content deleted Content added
m WP:CHECKWIKI error fix for #61. Punctuation goes before References. Do general fixes if a problem exists. - using AWB (8853) |
changed section on closure properties to properties and added another property |
||
Line 46:
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 concave 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>.
==
# 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 functions defined by <math>g(S)=\min(f(S),c)</math>, where <math>c</math> is a non-negative real number and <math>g(S)=f(\Omega \setminus S)</math> are also submodular.
# 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.
== Optimization problems ==
| |||