Polynomial-time Approximation Scheme

computation

Definition

Polynomial-time Approximation Scheme

An approximation scheme $\mathcal{A}$ is a polynomial-time approximation scheme if, for every fixed constant $\epsilon >0$, the running time of $\mathcal{A}$ is polynomial in the input size $|I|$.

Equivalently,

$$T_{\mathcal{A}}(|I|,\epsilon )=|I{|}^{g(\epsilon )}$$

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

Meaning

Why polynomial

In a PTAS, the error parameter $\epsilon$ is fixed first. After that, the algorithm runs in polynomial time in $|I|$.

The important restriction is only with respect to $|I|$. The dependence on $\epsilon$ may still be very bad.

Examples

PTAS but not EPTAS

The running time $|I{|}^{1/\epsilon }$ is a PTAS, because for every fixed $\epsilon$ it is polynomial in $|I|$.

It is not an EPTAS, because the exponent of $|I|$ depends on $\epsilon$.