---

劣モジュラ性について

概要

• 一言で表すと集合に加わる要素が増えると、増えるに従って集合の大きさの増加が減少する関数
• 凸関数と似た性質を持つので、ゲーム理論や機械学習と相性がいい
• 組み合わせ最適の問題などが該当することがある

定式化

\(f(A + i) - f(A) \geq f(A + i + j) - A(A + j)\)

• すでにA+jを持っている人のほうがiが追加されたときの嬉しさの増加量が少ない

上の式を整理すると

\[f(A) + f(B) \geq f(A \cup B) + f(A \cap B)\]

貪欲アルゴリズムによる近似

\(f(S_k)\geq \left(1-\dfrac{1}{e}\right)f(S^*)\)

• \(S_k\); 貪欲アルゴリズムによる近似解
• \(S^*\); 最適値

証明は参考¹から確認できる

参考

• 劣モジュラ関数最大化に対する貪欲アルゴリズム/mathwords
• 集合関数，劣モジュラ性とは
• 劣モジュラ関数/Wikipedia