Polynomial-time approximation schemes

Wed, May 4, 2016 02:00 CEST

Tags: Approximation Algorithms

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} $$