多項式時間近似スキーム

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

PTASの実行時間は、εを固定すると、問題の大きさ n の多項式であることが求められるが、εに対しては定められていない。このため、実行時間がO(n1/ε) や O(nexp(1/ε)) であっても、PTASである。

変形[編集]

決定的[編集]

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

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

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

別の決定論的なPTASの変形として、準多項式時間近似スキーム (quasi-polynomial-time approximation scheme または QPTAS) がある。QPTASはある固定されたεに対してn^{polylog(n)}の時間複雑度を持つ。

乱択[編集]

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

参考文献[編集]

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

外部リンク[編集]