子模集合函数(Submodular set function)
子模函数是一个集合函数,有减小回转属性(diminishing returns ),适用于多种应用,包括近似算法,博弈理论(函数建模)和电网络。定义如果Ω是一个集合,一个子模函数是一个集合函数, f:2Ω→R\ f :2^Ω \to \mathbb R ,其中 2Ω\ 2^Ω 表示集合Ω的幂集,满足一下等式:1.对所有X,Y⊆Ω,其中X⊆Y,则对所有x∈Ω∖Y有f(X∪{x})−f(X)≥f(Y