多項式時間近似スキーム

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