jjzjj

Supermodular

全部标签

子/次模 (Submodular)、超模 (Supermodular)和模(Modular)函数

定义  子模(Submodular)、超模(Supermodular)和模(Modular)函数是组合优化中用到的集合函数概念。函数定义域为某个有限集$\Omega$的幂集$2^\Omega$,值域通常为$R$,即$f:2^\Omega\toR$。  子模函数:对于集合$A\subseteqB\subset\Omega$,元素$e\in\Omega-B$,子模函数$f(X)$满足$f(A\cup\{e\})-f(A)\geqf(B\cup\{e\})-f(B)$  直观上看,随着集合$X$元素的增加,在新增某个元素时$f(X)$值的变化量不变或降低。或者说函数$f(X)$的边际效应逐渐降低。需