Definition
Polynomial-time Approximation Scheme
An approximation scheme
is a polynomial-time approximation scheme if, for every fixed constant , the running time of is polynomial in the input size . Equivalently,
for some function
that depends only on .
Meaning
Why polynomial
In a PTAS, the error parameter
is fixed first. After that, the algorithm runs in polynomial time in . The important restriction is only with respect to
. The dependence on may still be very bad.
Examples
PTAS but not EPTAS
The running time
is a PTAS, because for every fixed it is polynomial in . It is not an EPTAS, because the exponent of
depends on .