Polynomial-time approximation schemes

Wed, May 4, 2016

PTAS

\((1\pm\varepsilon)\)-approximation with complexity \(O(n^{f(\varepsilon)})\).

EPTAS

\((1\pm\varepsilon)\)-approximation with complexity \(O(f(\varepsilon) n^c)\).

FPTAS

\((1\pm\varepsilon)\)-approximation with complexity \(O(poly(\frac{1}{\varepsilon}) n^c)\).

\[ \text{FPTAS} \subseteq \text{FPT} \]