Approximation Schemes

Is a more sophisticated version of an Approximation Algorithm that allows users to control the trade-off between running time and Approximation Ratio.

Formally it is an approximation algorithm that, in addition to taking an instance of the problem as input, also takes a value $\epsilon >0$ such that for any fixed $\epsilon$, the scheme is a $(1+\epsilon )$ approximation algorithm.

Polynomial-time Approximation Scheme

We say that an approximation scheme is a polynomial-time approximation scheme if for any fixed $\epsilon >0$, the scheme runs in time polynomial in the size $n$ of its input instance.

Fully polynomial-time approximation scheme

We call an approximation scheme a fully polynomial-time approximation scheme if its running time is polynomial in both $1/\epsilon$ and the size $n$ of its input instance.

With such a scheme any constant-factor decrease in $\epsilon$ comes with a corresponding constant-factor increase in running time.