FPTAS は 0-1 ナップザックのような弱い NP 問題に適用できることがわかりました。
しかし、ビン パッキングのような強力な NP 問題に同じ原則を適用できないのはなぜですか。同じことについて wiki ページもチェックしましたが、ほとんど理解していませんでした。
質問する
331 次
1 に答える
2
強力な NP 完全問題に FPTAS がある場合、近似アルゴリズムを「だまして」最適解を与えることができます。詳細はこちら: http://www.idi.ntnu.no/~mlh/algkon/complexity.pdf
この FPTAS の存在により、NP 完全問題の多項式時間アルゴリズムが得られます。
于 2013-11-01T17:50:11.700 に答える