PTAS, FPTAS and APX

Fix a finite-instance optimization problem in the model of Optimization problems and approximation ratios.

• A polynomial-time approximation scheme (PTAS) is a family $(A_{ϵ}{)}_{0<ϵ<1}$ of algorithms such that for every fixed $ϵ$ with $0<ϵ<1$ the algorithm $A_{ϵ}$ runs in deterministic time polynomial in the input length and guarantees factor $1+ϵ$ for minimization, respectively $1-ϵ$ for maximization, in the value inequalities of Optimization problems and approximation ratios. The order of quantifiers is that the exponent of the polynomial may depend on the fixed $ϵ$.
• A fully polynomial-time approximation scheme (FPTAS) is a PTAS with one running-time bound that is a polynomial jointly in the input length and in $1\mathrm{/}ϵ$.
• APX denotes, by explicit local convention, the class of finite-instance optimization problems in that model that admit one polynomial-time fixed-factor approximation in the objective direction of Optimization problems and approximation ratios: a rational $\rho \ge 1$ with a polynomial-time $\rho$-approximation for a minimization problem, or a rational $0<\rho \le 1$ with a polynomial-time $\rho$-approximation for a maximization problem. This is a selected convention for this page; it does not claim that all of the literature uses the same reduction-based notion of APX-hardness.

Since every FPTAS is a PTAS, a problem with no PTAS (unless $P=NP$) also has no FPTAS unless $P=NP$. All value guarantees above use the inequalities of Optimization problems and approximation ratios and therefore include $\mathrm{OPT}=0$ without forming a quotient by $\mathrm{OPT}$. PTAS or FPTAS existence, by itself, proves neither APX-hardness nor APX-completeness of any target; those notions are defined separately on this page, under a declared reduction notion, and are not derived here.