劣モジュラ関数

提供:ORWiki
移動: 案内, 検索

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

分配束 {\mathcal D}\, 上の関数 f\, が, 任意の X,Y\in{\mathcal D}\, に対して


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


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

個人用ツール