next up previous
: この文書について... : appr : `なるべく最大に近い`とは?

近似アルゴリズムの存在性(研究の内容)

多項式時間のアルゴリズムが知られていない問題のすべてが, 倍率の良い (すなわち, なるべく1に近い)近似アルゴリズムを持つのだろうか? それともある問題は持つが, 別の問題は持たないというように問題毎に 違うのだろうか?もしそうならば, どのような問題が倍率の良い 近似アルゴリズムを持つのだろうか, またその本質的な違いは何だろうか?

Koichi Yamazaki 平成12年3月15日