コンピュータサイエンス（特にアルゴリズム）において、多項式時間近似スキーム（PTAS ）は、最適化問題（ほとんどの場合、NP困難な最適化問題） に対する近似アルゴリズムの一種です
巡回セールスマン問題（PTAS）は、最適化問題のインスタンスとパラメータε > 0を受け取り、最適解から1 + ε （最大化問題の場合は1 - ε ）の係数以内の解を生成するアルゴリズムです。例えば、ユークリッド巡回セールスマン問題の場合、PTASは長さが最大で(1 + ε) Lの巡回経路を生成します。ここで、Lは最短巡回経路の長さです。[1]
PTASの実行時間は、εが一定であれば問題の大きさの多項式となる必要があるが、εが異なると実行時間は異なる場合がある。したがって、実行時間がO ( n 1/ε )、あるいはO ( n exp(1/ε) )で済むアルゴリズムもPTASとみなされる。
バリアント
決定論的
PTASアルゴリズムの実際的な問題は、例えば実行時間がO ( n (1/ε)! )の場合、εが小さくなるにつれて多項式の指数が劇的に増加する可能性があることです。これに対処する1つの方法は、効率的な多項式時間近似スキーム、つまりEPTASを定義することです。EPTASでは、 εに依存しない定数cに対して実行時間がO ( nc )である必要があります。これにより、問題のサイズが大きくなると、使用されているεに関係なく、実行時間に同じ相対的な影響があることが保証されます。ただし、 big-Oの下の定数は、依然としてεに任意に依存する可能性があります。言い換えれば、EPTASは、パラメータがεである FPT時間で実行されます
さらに制限が厳しく、実際に有用なのは、完全多項式時間近似スキーム、つまりFPTASです。このスキームでは、アルゴリズムが問題のサイズnと1/ε の両方で多項式であることが必要です。
P = NPでない限り、 FPTAS ⊊ PTAS ⊊ APXが成り立ちます。[2]したがって、この仮定の下では、APX困難な問題にはPTASは存在しません。
PTASのもう一つの決定論的変種は、準多項式時間近似スキーム、すなわちQPTASである。QPTASは、各固定ε > 0に対して、時間計算量 n polylog ( n )を持つ。さらに、PTASは問題のパラメータ化によってはFPT時間で実行可能であり、パラメータ化された近似スキームにつながる。
ランダム化
PTASを持たない問題の中には、同様の特性を持つランダム化アルゴリズム、すなわち多項式時間ランダム化近似スキーム（PRAS）が許容されるものがあります。PRASは、最適化問題または計数問題のインスタンスとパラメータε > 0を取り、多項式時間で最適値の係数ε以内にある確率の高い解を生成するアルゴリズムです。慣習的に、「高い確率」とは3/4を超える確率を意味しますが、ほとんどの確率的複雑性クラスと同様に、定義はこの正確な値の変動に対して堅牢です（最低限必要な要件は通常1/2より大きい）。PTASと同様に、PRASはnについて実行時間多項式を持つ必要がありますが、εについては必ずしもそうではありません。εについての実行時間にさらなる制限を加えることで、 EPTASに類似した効率的な多項式時間ランダム化近似スキーム（EPRAS）と、FPTASに類似した完全多項式時間ランダム化近似スキーム（FPRAS）を定義できます。[3]
複雑性クラスとして
PTASという用語は、PTASを持つ最適化問題のクラスを指すためにも使用される。PTASはAPXのサブセットであり、P = NPでない限り厳密なサブセットである。[2]
PTASへの帰属関係は、 PTAS縮約、L縮約、またはP縮約を用いて示せます。いずれもPTASへの帰属関係を保持するため、PTAS完全性の証明にも使用できます。一方、PTASへの帰属関係がない（つまり、PTASが存在しない）ことを示すには、問題がAPX困難であることを示すことで可能です。APX困難性は、通常、PTAS縮約またはAP縮約によって示されます。
参照
- パラメータ化近似法、 FPT時間で実行される近似法
参考文献
- ^ サンジーヴ・アローラ、「ユークリッドTSPおよびその他の幾何学的問題のための多項式時間近似スキーム」、Journal of the ACM 45(5) 753–782、1998年
- ^ ab Jansen, Thomas (1998)、「複雑性理論と近似アルゴリズム入門」、Mayr, Ernst W.、Prömel, Hans Jürgen、Steger, Angelika (編)、『証明検証と近似アルゴリズムに関する講義』、Lecture Notes in Computer Science、vol. 1367、Springer、pp. 5– 28、doi :10.1007/BFb0053011、ISBN 978354064201520ページの定義1.30に続く議論を参照してください。
- ^ Vazirani, Vijay V. (2003).近似アルゴリズム. ベルリン: Springer. pp. 294– 295. ISBN 3-540-65367-8。
外部リンク
- 複雑性動物園：PTAS、EPTAS
- Pierluigi Crescenzi、Viggo Kann、Magnús Halldórsson、Marek Karpinski、Gerhard Woeginger、「NP最適化問題の概要- どのNP最適化問題にPTASがあるかをリストします。」
