a polynomial-time approximation scheme (PTAS)
A fixed approximation ratio (2 for vertex cover, ln n for set cover) gives you whatever accuracy the algorithm happens to deliver — take it or leave it. Some problems are friendlier: they let you DIAL IN the accuracy you want. A polynomial-time approximation scheme is a single algorithm with a knob, epsilon, that you set to any small positive value, and it promises a solution within a factor (1 + epsilon) of optimal — as close to perfect as you ask — while still running in polynomial time in the input size n.
Read the definition carefully, because the cost of accuracy hides in the running time. A PTAS takes both the instance and your chosen epsilon, and for EACH fixed epsilon it runs in time polynomial in n. The crucial subtlety is that the dependence on epsilon may be horrendous — the running time is allowed to blow up as epsilon shrinks, in ways like O(n^(1/epsilon)) or O(2^(1/epsilon) * n). So asking for epsilon = 0.5 (within 50%) might be fast, but epsilon = 0.01 (within 1%) could be astronomically slower, since 1/epsilon now sits in the exponent. The promise is only that, once you commit to a particular epsilon, the n-dependence is polynomial; the constant and exponent attached to that polynomial can be enormous functions of 1/epsilon. A typical PTAS works by exploiting structure: for some geometric and scheduling problems you can chop the instance into pieces small enough to solve near-optimally by brute force or dynamic programming, with the piece size governed by epsilon.
Why this distinction matters: a PTAS is a strong statement — it says the problem can be approximated arbitrarily well in polynomial time, so there is no fixed inapproximability barrier. That is a meaningfully better situation than vertex cover (stuck at a constant) or set cover (stuck at log n). But 'polynomial for each epsilon' is a weaker promise than it sounds; if the running time is n^(1/epsilon), the scheme is impractical for the high accuracy you would actually want. The stronger, more practical cousin that fixes this — making the running time polynomial in 1/epsilon too — is the FPTAS.
Suppose a PTAS for some problem runs in time O(n^(1/epsilon)). For epsilon = 1/2 it is O(n^2) — fine. For epsilon = 1/10 (within 10%) it is O(n^10) — already painful. For epsilon = 1/100 it is O(n^100) — useless in practice. The scheme is genuinely polynomial for each fixed epsilon, yet the exponent explodes as you demand more accuracy.
A PTAS is polynomial in n for each fixed epsilon, but may be exponential in 1/epsilon.
'Polynomial' in PTAS means polynomial in n for each FIXED epsilon — the 1/epsilon dependence is unrestricted and is often exponential, e.g. n^(1/epsilon). So a PTAS can be hopelessly slow at the high accuracy you actually want; the FPTAS is the version that fixes this.