PTAS

PTAS（Polynomial-time approximation scheme）：在計算複雜性理論中，PTAS是指針對最最佳化問題的一類近似算法。

基本介紹

• 中文名：近似算法
• 外文名：Polynomial-time approximation schemePTAS
• 外文簡稱：PTAS
• 中文全稱：一個多項式時間近似方案
• 分類：EPTAS
• FPTAS要求：對n和1/ε多項式要求高

基本概念

該算法的輸入為問題的實例以及一個任意小的值ε > 0，而算法的結果是一個近似度為 1 + ε的可行解；並且對於每一個固定的ε，算法運行時間複雜度對於實例的規模 n是多項式時間的。PTAS的運行時間只要求對輸入實例的規模n為多項式時間複雜度，而不考慮ε。因此當算法運行時間複雜度為 O(n^1/ε)甚至O(n^exp(1/ε)) 時，仍是PTAS算法。

包含方式

EPTAS

在實際問題中，採用PTAS算法往往會造成其多項式時間複雜度隨ε的減小而迅速增加，例如當時間複雜度為O(n^(1/ε)!) 時，時間複雜度會增加很迅速。因此，定義了Efficient Polynomial-Time Approximation Scheme（EPTAS），EPTAS要求時間複雜度為O(n^c)，其中c是與ε無關的常量。這樣確保了運行時間只隨輸入規模變化而變化，而與ε無關。

FPTAS

但在big-O限制下，常量c仍有可能取決於ε，因此更為嚴格，在實際問題中用途更廣的定義是Fully Polynomial-Time Approximation Scheme（FPTAS），FPTAS要求算法對問題規模n和1/ε都是多項式時間複雜度的。