劣モジュラ関数
ベクトル x = { x 1 , x 2 , ... , x n } {\displaystyle \mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}} であって、各要素が 0 ≤ x i ≤ 1 {\displaystyle 0\leq x_{i}\leq 1} となるものに対し、 f L ( x ) = E ( f ( { i : x i ≥ λ } ) ) {\displaystyle f^{L}(\mathbf {x} )=\mathbb {E} (f(\{i:x_{i}\geq \lambda \}))} で定義される関数を集合関数 f {\displaystyle f} のロバース拡張 (Lovász extension) という。この関数は閉区間 [ 0 , 1 ] {\displaystyle [0,1]} 上の一様分布から λ {\displaystyle \lambda } 以上のものを選んだ時の期待値を返すような関数になっており、この関数は凸関数になる。
f ( S ) = min ( B , ∑ i ∈ S w i ) {\displaystyle f(S)=\min \left(B,\sum _{i\in S}w_{i}\right)} という形で表せる関数のうち、 w i ≥ 0 , B ≥ 0 {\displaystyle w_{i}\geq 0,B\geq 0} を満たす関数。
単調関数でない劣モジュラ関数。
集合 Ω = { E 1 , E 2 , ... , E n } {\displaystyle \Omega =\{E_{1},E_{2},\ldots ,E_{n}\}} が何らかの元集合 Ω ′ {\displaystyle \Omega '} の部分集合族であるとする。これに対して、 f ( S ) = | ⋃ E i ∈ S E i | {\displaystyle f(S)=|\bigcup _{E_{i}\in S}E_{i}|} for S ⊆ Ω {\displaystyle S\subseteq \Omega } という形で表せる関数。
単調でも対称でもない劣モジュラ関数。 以下、非対称な劣モジュラ関数の例である。