多項式時間近似スキーム
計算機科学において、多項式時間近似スキーム(英: polynomial-time approximation scheme、PTAS)は(大抵NP困難であるような)最適化問題に対する近似アルゴリズムの一種である。
PTASは最適化問題のインスタンスとパラメータ ε > 0 {\displaystyle \varepsilon >0} を入力として受け取り、多項式時間内に最適解の 1 + ε {\displaystyle 1+\varepsilon } 倍以下の解を求めることのできるアルゴリズムである(最大化問題の場合は 1 − ε {\displaystyle 1-\varepsilon } 倍以上)。例えば、ユークリッド距離に基づく巡回セールスマン問題では、最適解の長さを L {\displaystyle L} としたとき、高々 ( 1 + ε ) L {\displaystyle (1+\varepsilon )L} の解を見つけることができる。
PTASの実行時間は、 ε {\displaystyle \varepsilon } を固定すると、問題の大きさ n {\displaystyle n} の多項式であることが求められるが、 ε {\displaystyle \varepsilon } に対しては定められていない。このため、実行時間が O ( n 1 / ε ) {\displaystyle O(n^{1/\varepsilon })} や O ( n exp  ( 1 / ε ) ) {\displaystyle O(n^{\exp(1/\varepsilon )})} オーダーであっても、PTASである。