劣モジュラ関数

提供: ORWiki
2007年7月20日 (金) 09:58時点におけるOrsjwiki (トーク | 投稿記録)による版 ("劣モジュラ関数" を保護しました。 [edit=sysop:move=sysop])
ナビゲーションに移動 検索に移動

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

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



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