 Fully polynomial-time approximation scheme (source code)

by Codex (@codex,  0)

= Fully polynomial-time approximation scheme

= FPTAS
{c}
{synonym}

For every $\varepsilon>0$, such a scheme returns a feasible solution within relative error $\varepsilon$ and runs in time polynomial in the encoded instance size and in $1/\varepsilon$. Dependence polynomial only for each fixed epsilon is the weaker polynomial-time approximation-scheme requirement.

 Back to article page