Algorithms/ApproximationAlgorithm - tmura's note - atwiki（アットウィキ）

Algorithms > ApproximationAlgorithm

近似アルゴリズム

近似度

入力 $x$ に対する近似アルゴリズム $A$ のコストを $C_A(x)$ 、
また（計算時間を無視すれば求めることのできる）厳密解のコストを $O_{OPT}(x)$ とする。
任意の $x$ に対して、ある定数 $d \geq 0$ が存在して、
$C_A(x) \leq rC_{OPT}(x) + d$
が成り立つとき、 $A$ の近似度は $r$ であるという。

ここで、コストは計算量を表すのではない。（それだと「近似度」というネーミングが不適切だし）。
例えばビン詰問題においては、ビンの本数をコストとする。

代表的な問題

ビン詰問題 (Bin-Packing Problem)

入力が $n$ 個の数（アイテムと呼ばれる） $u_1,u_2,\cdots,u_n (0 < u_i < \leq 1.0)$ で与えられ、
ビンの容量を1.0とする。できるだけ少ないビンを使って、全てのアイテムを詰め込むには?

初適合アルゴリズムの近似度に関する定理: 初適合アルゴリズムとは、各アイテムについて、途中までしか詰まってない全てのビンを順に見ていって、; 最初に適合した（そのアイテムを詰められる容量が空いている）ビンに詰める方法である。; 初適合アルゴリズムの近似度は7/4(=1.75)以下である。（実は、近似度=1.7の証明があるらしい。）

集合被覆問題(Set Cover Problem)

イメージとしては、
複数種類の部品を全て調達するために、最低何社の部品メーカーと契約すればよいか?という問題である。

正確に書くと、入力は集合 $U={u_1,u_2,\cdots,u_n}$ と
$k$ 個の $U$ の部分集合 $S_1,S_2,\cdots,S_k (S_i \subseteq U)$ で、
$S_{i_1} \cup S_{i_2} \cup \cdots \cup S_{i_j} = U$ となる最小個数の
$S_{i_1},S_{i_2},\cdots,S_{i_j}$ を求めよ、という問題である。

集合被覆問題に対しては、まだカバーできていない $U$ の要素を一番多くカバーする $S_i$ から
順に選んでいくという典型的な貪欲アルゴリズムが非常に有効であり、
これよりも本質的に良いアルゴリズムは知られていない。

定理: 上述の貪欲アルゴリズムの近似度は $1 + \ln n$ 以下である。

分割問題

整数の集合が与えられたとき、その要素の和が等しくなるように集合を２つに分割せよ、という問題。

形式的に書くと、整数の集合 $X = {i_1,i_2,\cdots,i_n}$ が与えられたとき、
その部分集合 $Y \subseteq X$ に対してその中の整数の和を $\sigma(Y)$ 、
つまり、 $\sigma(Y) = \sum_{i_j \in Y}i_j$ とおき、
$\sigma(Y) = \sigma(X - Y)$
であるような $Y$ を求めよという問題である。解がない場合も当然起こりうる。