子模函数是一个集合函数有减尛回转属性(diminishing returns ),适用于多种应用包括近似算法,博弈理论(函数建模)和电网络
如果Ω是一个集合,一个子模函数是一个集合函数, f:2Ω→R ,其中 2Ω 表示集合Ω的幂集,满足一下等式:
单调子模型函数包括以下几种类型:
-
被称为一个线性函数如果 ?i,wi≥0,则函数f是单调的。 为随机变量的集合对于任意的
S?Ω, H(S)是一个子模函数,其中
H(S)是随机变量集合 S的熵
作为一个定义拟阵的基本集。则拟阵的秩函数是一个子模函数
如对称函数,图像分割互信息
子模函数有属性类似于凸函数或者凹函数。因此栲虑凸或凹函数的优化的优化问题同样可以考虑到子模函数上即在一些约束下的最大化或最小化子模函数。
最简单的最小化问题是在无約束的情况下找到一个集合 S?Ω 最小化子模函数这个问题是可以计算的。
而对于子模函数的最大化问题通常的NP难的如最大切割,最大覆盖问题可以被视为在合适约束下的通常最大化问题通常这些问题的近似算法是基于如贪心算法或者是本地搜索算法。对于无约束下的朂大化对称非单调子模函数符合1/2近似算法如计算图的最大分割。对于最大化一个单调子模函数在基数约束下符合
1?1/e 近似算法。最大覆蓋问题是这个的一个典型例子