next up previous
: 近似アルゴリズムの存在性(研究の内容) : appr : 近似アルゴリズム(Betterな解を求める)

`なるべく最大に近い`とは?

`なるべく最大に近い`ということを具体的に表す方法として例えば,
(1)最適解(Bestの解)の少なくとも90%程度の大きさの解を出力することを 保証する
か, もっと緩い基準で,
(2)最適解の1/log nよりは大きい解を出力することを保証する
などが考えられる. (1)の場合, 常に最適解の9/10よりは大きい解を出力することが保証されていて, この倍率9/10は入力のサイズnに依存しない. (2)の場合, nが大きくなればなるほど倍率1/log nは悪くなる. しかし差1/log n - 1/log (n+1)は小さくなる. 条件としては(1)の方が厳しく, (2)の方が緩い.

Koichi Yamazaki 平成12年3月15日