Families of Approximation Algorithms

There are well-known families of approximation algorithms.

PTAS (Polynomial-Time Approximation Scheme)

A $\operatorname{PTAS}$ is a family of algorithms that achieves a $(1 + \epsilon)$-approximation for minimization problems and a $(1 - \epsilon)$-approximation for maximization problems. The running time may depend on $\epsilon$, but must be polynomial in the input size (without any polynomial restriction on $\epsilon$).

FPTAS (Fully Polynomial-Time Approximation Scheme)

An $\operatorname{FPTAS}$ is a $\operatorname{PTAS}$ whose running time is also bounded by a polynomial in $\frac{1}{\epsilon}$.

Reference :David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms

Reference :CSI6107 lecture at Yonsei University