多項式時間近似スキーム

計算機科学において、多項式時間近似スキーム（英: polynomial-time approximation scheme、PTAS）は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。

PTASは最適化問題のインスタンスとパラメータ ${\displaystyle \varepsilon >0}$ を入力として受け取り、多項式時間内に最適解の ${\displaystyle 1+\varepsilon }$ 倍以下の解を求めることのできるアルゴリズムである（最大化問題の場合は ${\displaystyle 1-\varepsilon }$ 倍以上）。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを ${\displaystyle L}$ としたとき、高々 ${\displaystyle (1+\varepsilon )L}$ の解を見つけることができる。^[1]

PTASの実行時間は、${\displaystyle \varepsilon }$ を固定すると、問題の大きさ ${\displaystyle n}$ の多項式であることが求められるが、${\displaystyle \varepsilon }$ に対しては定められていない。このため、実行時間が ${\displaystyle O(n^{1/\varepsilon })}$ や ${\displaystyle O(n^{\exp(1/\varepsilon )})}$ オーダーであっても、PTASである。

変形

決定的

PTASアルゴリズムがある現実的な問題は、εを小さくすると多項式の指数部が劇的に大きくなってしまう（例えば ${\displaystyle O(n^{(1/\varepsilon )!})}$ のように）。この問題に対処するひとつの方法が効率的な多項式時間近似スキーム（EPTAS^[2]）と呼ばれる、実行時間が ${\displaystyle c}$ を ${\displaystyle \varepsilon }$ と独立な定数として、${\displaystyle O(n^{c})}$ であるようなアルゴリズムである。この場合、どのようなεを選んでも問題の大きさは実行時間に与える影響は等しくなる。しかし、O記法における定数はεに対して任意に大きくなりうる。これに対してより強い制約として、実行時間が問題の大きさ ${\displaystyle n}$ と ${\displaystyle 1/\varepsilon }$ 両方の多項式時間であるものを完全多項式時間近似スキーム（FPTAS^[3]）と呼ぶ。 ナップサック問題はFPTASがある問題の例である.

多項式的に有界な目的関数を持つどんな強度にNP困難な最適化問題も、P=NPでない限り、FPTASを持ち得ない。^[4] しかし、逆は真ではない。例えば、P≠NPのとき、2つの制約をもつナップサック問題はFPTASを持たないが、たとえ目的関数が多項式的に有界の場合でも強度にNP困難ではない。^[5]

P=NPでない限り、${\displaystyle FPTAS\subsetneq PTAS\subsetneq APX}$ が成り立つ。すなわち、同じ仮定の下で、APX困難な問題はPTASを持たない。

別の決定論的なPTASの変形として、準多項式時間近似スキーム（QPTAS^[6]）がある。QPTASはある固定された ${\displaystyle \varepsilon }$ に対して${\displaystyle n^{polylog(n)}}$の時間複雑度を持つ。

乱択

PTASを持たない問題が、PTASと似通った特徴を持つ多項式時間乱択近似スキーム（PRAS^[7]）を持つことがある。PRASは最適化問題のインスタンスとパラメータ ${\displaystyle \varepsilon >0}$ を入力とし、多項式時間で『高い確率』で最適解の ${\displaystyle 1+\varepsilon }$ 倍以下のソリューションを生成することのできるアルゴリズムである。『高い確率』とは慣習的に ${\displaystyle 3/4}$ 以上のことであるが、ほとんどの確率的計算複雑度のクラスは、この具体的な値に対してロバストである。PTASと同様にPRASは問題のサイズ ${\displaystyle n}$ に対して多項式の計算時間を持たねばならないが、${\displaystyle \varepsilon }$ に対してはそうではない。${\displaystyle \varepsilon }$ に対するEPTASと同様の制約を持つものを効率的多項式時間乱択近似スキーム（EPRAS^[8]）と呼ぶ。また、FPTASと同様の制約を持つものを完全多項式時間乱択近似スキーム（FPRAS^[9]）と呼ぶ。^[4]

脚注

1. ^ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.
2. ^ 英: efficient polynomial-time approximation scheme
3. ^ 英: fully polynomial-time approximation scheme
4. ^ ^{a b} Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. pp. 294–295. ISBN 3-540-65367-8 
5. ^ H. Kellerer and U. Pferschy and D. Pisinger (2004). Knapsack Problems. Springer 
6. ^ 英: quasi-polynomial-time approximation scheme
7. ^ 英: polynomial-time randomized approximation scheme
8. ^ 英: efficient polynomial-time randomized approximation scheme
9. ^ 英: fully polynomial-time randomized approximation scheme

外部リンク

• Complexity Zoo: PTAS, EPTAS, FPTAS
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger, A compendium of NP optimization problems – list which NP optimization problems have PTAS.