|
計算機科学において、多項式時間近似スキーム (polynomial-time approximation scheme, 以後PTASと呼ぶ) は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。 PTASは最適化問題のインスタンスとパラメータε > 0 を入力として受け取り、多項式時間内に最適解の 1 + ε倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は 1 - ε倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを''L''としたとき、高々(1 + ε)''L''の解を見つけることができる。〔Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.〕 PTASの実行時間は、εを固定すると、問題の大きさ ''n'' の多項式であることが求められるが、εに対しては定められていない。このため、実行時間が''O''(''n''1/ε) や ''O''(''n''exp(1/ε)) であっても、PTASである。 ==変形== ===決定的=== PTASアルゴリズムがある現実的な問題は、εを小さくすると多項式の指数部が劇的に大きくなってしまう(例えば''O''(''n''(1/ε)!)のように)。この問題に対処するひとつの方法が効率的な多項式時間近似スキーム (efficient polynomial-time approximation scheme, またはEPTAS)と呼ばれる、実行時間が ''c'' をεと独立な定数として、''O''(''n''''c'') であるようなアルゴリズムである。この場合、どのようなεを選んでも問題の大きさは実行時間に与える影響は等しくなる。しかし、''O''記法における定数はεに対して任意に大きくなりうる。これに対してより強い制約として、実行時間が問題の大きさ ''n'' と 1/ε両方の多項式時間であるものを完全多項式時間近似スキーム (fully polynomial-time approximation scheme または FPTAS) と呼ぶ。 ナップサック問題はFPTASがある問題の例である. 多項式的に有界な目的関数を持つどんな強度にNP困難な最適化問題も、P=NPでない限り、FPTASを持ち得ない。〔 しかし、逆は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。 P=NPでない限り、FPTAS ⊊ PTAS ⊊ APXが成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。 別の決定論的なPTASの変形として、準多項式時間近似スキーム (quasi-polynomial-time approximation scheme または QPTAS) がある。QPTASはある固定されたεに対しての時間複雑度を持つ。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「多項式時間近似スキーム」の詳細全文を読む スポンサード リンク
|