劣モジュラ関数

提供: ORWiki
2008年11月14日 (金) 09:44時点におけるAlbeit-Kun (トーク | 投稿記録)による版
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
ナビゲーションに移動 検索に移動

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

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



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