「劣モジュラ関数」の版間の差分

提供: ORWiki
ナビゲーションに移動 検索に移動
1行目: 1行目:
 
'''【れつもじゅらかんすう (submodular function)】'''
 
'''【れつもじゅらかんすう (submodular function)】'''
  
−
分配束 <math>{\cal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\cal D}\,</math> に対して
+
分配束 <math>{\mathcal D}\,</math> 上の関数 <math>f\,</math> が, 任意の <math>X,Y\in{\mathcal D}\,</math> に対して
  
  

2007年7月11日 (水) 18:18時点における版

【れつもじゅらかんすう (submodular function)】

分配束 上の関数 が, 任意の に対して


\[ f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y) \]

を満たすとき, を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

「https://orsj-ml.org/orwiki/wiki/index.php?title=劣モジュラ関数&oldid=2672」から取得