Efficient Polynomial-time Approximation Scheme

computation

Definition

Efficient Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is called an efficient polynomial-time approximation scheme if its running time has the form

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

for some function $f$ that depends only on $\epsilon$.

Equivalently, an EPTAS is a PTAS whose polynomial degree in $|I|$ does not depend on $\epsilon$.

Efficiency

Why efficient?

In a plain PTAS, the exponent of $|I|$ may depend on $\epsilon$.

In an EPTAS, this is forbidden. All dependence on $\epsilon$ is moved into the factor $f\left(\frac{1}{\epsilon }\right)$, while the dependence on $|I|$ stays polynomial with fixed degree.

Examples

EPTAS but not FPTAS

The running time $2^{1/\epsilon }\cdot |I{|}^3$ is an EPTAS, because it has the form $f\left(\frac{1}{\epsilon }\right)\cdot |I{|}^{O(1)}$.

It is not an FPTAS, because the dependence on $\frac{1}{\epsilon }$ is exponential rather than polynomial.

PTAS but not EPTAS

The running time $|I{|}^{1/\epsilon }$ is a PTAS, but not an EPTAS.