基多面体

【きためんたい (base polyhedron)】

有限集合 $N\,$ 上の実数値関数全体のなす線形空間を $\mathbf{R}^N\,$ と表す. 劣モジュラシステム $(\mathcal{D},f)\,$ は, $\mathbf{R}^N\,$ 中の基多面体

$\mathbf{B}(f)=\{x\, \mid x\in\mathbf{R}^N,\sum_{i\in N}x(i)=f(N),\,$

$\forall X\in\mathcal{D}:\sum_{i\in X}x(i)\leq f(X)\}\,$

を定める. 基多面体上では, 貪欲アルゴリズムによって線形目的関数の最適化が可能である.