「劣モジュラ関数」の版間の差分
ナビゲーションに移動
検索に移動
(新しいページ: ''''【れつもじゅらかんすう (submodular function)】''' 分配束 ${\cal D}$ 上の関数 $f$ が, 任意の $X,Y\in{\cal D}$ に対して \[ f(X)+f(Y)\geq f(X\cup...') |
|||
| 1行目: | 1行目: | ||
'''【れつもじゅらかんすう (submodular function)】''' | '''【れつもじゅらかんすう (submodular function)】''' | ||
| − | 分配束 | + | 分配束 <math>{\cal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\cal D}\,</math> に対して |
| 8行目: | 8行目: | ||
\] | \] | ||
| − | を満たすとき, | + | を満たすとき, <math>f\,</math> を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である. |
2007年7月11日 (水) 14:42時点における版
【れつもじゅらかんすう (submodular function)】
分配束 上の関数 が, 任意の に対して
\[
f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)
\]
を満たすとき, を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.