Submodular set function: Difference between revisions

Revision as of 02:03, 12 November 2022

Revision as of 14:32, 9 January 2023

Line 18:

=== Monotone ===

A submodularset function <math>f</math> is ''monotone'' if for every <math>T\subseteq S</math> we have that <math>f(T)\leq f(S)</math>. Examples of monotone submodular functions include:

; Linear (Modular) functions : Any function of the form <math>f(S)=\sum_{i\in S}w_i</math> is called a linear function. Additionally if <math>\forall i,w_i\geq 0</math> then f is monotone.

; [[Budget-additive valuation|Budget-additive functions]] : Any function of the form <math>f(S)=\min\left\{B,~\sum_{i\in S}w_i\right\}</math> for each <math>w_i\geq 0</math> and <math>B\geq 0</math> is called budget additive.<ref name="BF" />