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