基多面体のソースを表示

'''【きためんたい (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}
\]

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