基多面体のソースを表示

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

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


<center>
<table>
<tr>
<td align="right"><math>\mathbf{B}(f)=\{x\, \mid x\in\mathbf{R}^N,\sum_{i\in N}x(i)=f(N),\,</math></td>
</tr>
<tr>
<td align="right"><math>\forall X\in\mathcal{D}:\sum_{i\in X}x(i)\leq f(X)\}\,</math></td></tr>
</table>
</center>


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