劣モジュラ関数

提供: ORWiki
2007年7月17日 (火) 11:25時点における122.17.2.240 (トーク)による版
ナビゲーションに移動 検索に移動

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

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



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