基本概念

EPTAS (Efficient PTAS)

FPTAS (Fully PTAS)

基本概念

PTAS（Polynomial-time approximation scheme）：在计算复杂性理论中，PTAS是指针对最优化问题的一类近似算法。该算法的输入为问题的实例以及一个任意小的值ε > 0，而算法的结果是一个近似度为 1 + ε的可行解；并且对于每一个固定的ε，算法运行时间复杂度对于实例的规模 n是多项式时间的。PTAS的运行时间只要求对输入实例的规模n为多项式时间复杂度，而不考虑ε。因此当算法运行时间复杂度为 O(n^1/ε)甚至O(n^exp(1/ε)) 时，仍是PTAS算法。

EPTAS (Efficient PTAS)

在实际问题中，采用PTAS算法往往会造成其多项式时间复杂度随ε的减小而迅速增加，例如当时间复杂度为O(n^(1/ε)!) 时，时间复杂度会增加很迅速。因此，定义了Efficient Polynomial-Time Approximation Scheme（EPTAS），EPTAS要求时间复杂度为O(n^c)，其中c是与ε无关的常量。这样确保了运行时间只随输入规模变化而变化，而与ε无关。

FPTAS (Fully PTAS)

但在big-O限制下，常量c仍有可能取决于ε，因此更为严格，在实际问题中用途更广的定义是Fully Polynomial-Time Approximation Scheme（FPTAS），FPTAS要求算法对问题规模n和1/ε都是多项式时间复杂度的。