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