多項式時間近似算法

在計算機科學領域，多項式時間近似算法（PTAS）是一種用於優化問題（最常見的是NP-hard優化問題）的近似算法。

PTAS使用一個大於0的參數 ε，產生一個對於最小化問題能在 1 + ε 倍最優解內的解決方案（或最大化問題的 1 − ε 倍）。例如，對於歐幾里得旅行商問題，現有的最好PTAS 將產生一個長度最多為 (1 + ε) L 的解，其中L是最短行程的長度。 ε的大小越小，PTAS的近似性能比越靠近1，也即說明這個PTAS的計算結果越接近最優解。

對於一個固定大小的ε，PTAS 的運行時間必須是（對於問題大小）多項式的（例如對於一個原時間複雜度為O(2^n)的算法，它的PTAS時間複雜度可以為O(n⁴*2^k)，其中k為參數），但對於不同的 ε，可以是不同的。時間複雜度為O(n^1/ε) 甚至O(n^exp(1/ε)) 的算法同樣屬於 PTAS。