基多面体

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

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

\[ \begin{array}{ll} {\rm B}(f)=\{x & \mid x\in{\bf R}^N, \; \displaystyle{\sum_{i\in N}x(i)=f(N), }\\ & \hspace*{5mm} \forall X\in{\cal D}: \displaystyle{\sum_{i\in X}x(i)\leq f(X)} \} \end{array} \]

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