Fully Polynomial-time Approximation Scheme

computation

Definition

Fully Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is called a fully polynomial-time approximation scheme if its running time is polynomial in both the input size $|I|$ and $\frac{1}{\epsilon }$, i.e.:

$$T_{\mathcal{A}}(|I|,\epsilon )={\left(\frac{|I|}{\epsilon }\right)}^{O(1)}.$$

Equivalently, an FPTAS is a PTAS whose dependence on the error parameter is also polynomial.

Full

Why fully

In a PTAS, the running time must be polynomial in $|I|$ for every fixed $\epsilon >0$, but the degree of that polynomial may depend on $\epsilon$.

In an FPTAS, this is not allowed. The running time must remain polynomial even when $\epsilon$ is part of the input through $\frac{1}{\epsilon }$.

Consequence

Strength

Every FPTAS is a PTAS, but not every PTAS is an FPTAS.

For example, max-value knapsack has an FPTAS, while some other optimisation problems only admit a PTAS or no approximation scheme at all.

Examples

PTAS but not FPTAS

The running time

$$|I{|}^{1/\epsilon }$$

defines a PTAS, because for every fixed $\epsilon$ it is polynomial in $|I|$.

It is not an FPTAS, because it is not polynomial in $\frac{1}{\epsilon }$.

FPTAS

The running time

$$|I{|}^3\cdot {\left(\frac{1}{\epsilon }\right)}^2$$

is an FPTAS, because it is polynomial in both $|I|$ and $\frac{1}{\epsilon }$.