Definition
Efficient Polynomial-time Approximation Scheme
An approximation scheme
is called an efficient polynomial-time approximation scheme if its running time has the form for some function
that depends only on . Equivalently, an EPTAS is a PTAS whose polynomial degree in
does not depend on .
Efficiency
Why efficient?
In a plain PTAS, the exponent of
may depend on . In an EPTAS, this is forbidden. All dependence on
is moved into the factor , while the dependence on stays polynomial with fixed degree.
Examples
EPTAS but not FPTAS
The running time
is an EPTAS, because it has the form . It is not an FPTAS, because the dependence on
is exponential rather than polynomial.
PTAS but not EPTAS
The running time
is a PTAS, but not an EPTAS.