劣モジュラ関数最大化問題について、問題設定から詳しく解説します。劣モジュラ関数最大化では、単純な貪欲アルゴリズムの近似比が $\left(1-\dfrac{1}{e}\right)$ というきれいな値になります。
劣モジュラ関数最大化問題とは
ただし、$f$ は集合関数です。つまり、集合 $X=\{x_1,\dots,x_n\}$ の部分集合を入力として、実数値を返す関数とします。
また、$f$ は以下の性質を持つとします。
・単調
・非負値
・劣モジュラ
これらの意味は後述します。
この問題を劣モジュラ関数最大化問題と呼ぶことにします。
考える関数
・単調というのは「大きい集合の方が値が大きい」という意味です。
つまり、$A\subseteq B\subseteq X$ を満たす任意の $A$ と $B$ に対して、$f(A)\leq f(B)$ とします。
・非負というのは、出力が非負という意味です。
つまり、任意の $A\subseteq X$ に対して $f(A)\geq 0$ とします。
・劣モジュラ関数とは、任意の $A,B\subseteq X$ に対して
$f(A)+f(B)\geq f(A\cap B)+f(A\cup B)$
を満たす関数です。 劣モジュラ関数は、組合せ最適化の文脈などでしばしば登場します。
劣モジュラ関数最大化問題の難しさ
・劣モジュラ関数最大化問題は、NP困難です。最適な集合 $S^*$ を求めるのは非常に難しいです。
・貪欲アルゴリズムが、近似比 $\left(1-\dfrac{1}{e}\right)\fallingdotseq 0.63$ を達成します。つまり、最適値の $63$％以上の出力を保証する集合 $S$ を求めるのは簡単です。
ただし、貪欲アルゴリズム（Greedy Algorithm）とは、
・空集合から始めて
・要素を順々に１つずつ追加していく
・その際、各段階で関数が最大になるようにする
アルゴリズムです。
近似比1-1/eの証明
参考文献：When Greedy Algorithms are Good Enough
・貪欲アルゴリズムの各段階で得られる集合を $S_1,\dots,S_k$ と書きます。
・$S_i=\{s_1,\dots,s_i\}$ と書きます。
目標は、
$f(S_k)\geq \left(1-\dfrac{1}{e}\right)f(S^*)$
を示すことです。
また、$a_i=f(S^*)-f(S_i)$ とします。
（最適値と、貪欲アルゴリズムの途中までの出力値の差です）
証明は２段階からなります。
前半：$a_{i+1}\leq\left(1-\dfrac{1}{k}\right)a_i$ を示す。
後半：前半の不等式を使って、目標の式を示す。
証明の前半
青い不等式は「貪欲アルゴリズムで一歩進むと、最適値までの距離が、今までの $\left(1-\dfrac{1}{k}\right)$ 倍よりは近くなる」ことを表しています。
まず、単調性より、各 $i=1,\dots,k$ に対して
$f(S^*)\leq f(S^*\cup S_i)$
です。
ここで、$S^*=\{x_1,\dots,x_k\}$ とし、上式の右辺を「分解」していきます：
$f(S^*\cup S_i)\\
=f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_i\cup\{x_1,\dots,x_t\})-f(S_i\cup\{x_1,\dots,x_{t-1}\})\}$
上式のシグマの中身に劣モジュラの不等式（を移項したもの）を使うと、
$\leq f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_i\cup\{x_t\})-f(S_i)\}$
とつなげます。
さらに、貪欲アルゴリズムの定義より、
$\leq f(S_i)+\displaystyle\sum_{t=1}^k\{f(S_{i+1})-f(S_i)\}$
とつなげます。
以上を全てつなげると、
$f(S^*)\leq kf(S_{i+1})-(k-1)f(S_i)$
これを変形する（$a_i$ を使って表す）と、
$a_{i+1}\leq\left(1-\dfrac{1}{k}\right)a_i$
となります。
証明の後半
前半の不等式を繰り返し使うと、
$a_k\leq \left(1-\dfrac{1}{k}\right)^ka_0$
となりますが、
・$a_k=f(S^*)-f(S_k)$
・$a_0=f(S^*)-f(\phi)\leq f(S^*)$
・$1-\dfrac{1}{k}\leq e^{-\frac{1}{k}}$
なので、
$f(S^*)-f(S_k)\leq\dfrac{1}{e}f(S^*)$
となります。
これを整理すると
$f(S_k)\geq \left(1-\dfrac{1}{e}\right)f(S^*)$
となります。
次回は 一様な棒の慣性モーメントの計算方法と考察 を解説します。
