多項式時間近似算法

複雜度等級

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

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

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

參考

編輯
  1. ^ Sanjeev Arora, Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.