APX Optimisation Problem

Definition

APX Optimisation Problem

An NP-optimisation problem $\Pi$ is an APX optimisation problem if it belongs to the class APX: some polynomial-time algorithm $A$ returns a feasible solution within a fixed factor $c\ge 1$ of the optimum on every feasible instance $I$:

$$\{\begin{array}{ll}{\mathrm{OPT}}_{\Pi }(I)\le f_{\Pi }(I,A(I))\le c{\mathrm{OPT}}_{\Pi }(I),& \mathrm{goal}=\min ,\\ {\mathrm{OPT}}_{\Pi }(I)/c\le f_{\Pi }(I,A(I))\le {\mathrm{OPT}}_{\Pi }(I),& \mathrm{goal}=\max .\end{array}$$

Membership promises a constant approximation ratio, not arbitrarily small error or APX-hardness. Its associated decision version asks whether a feasible solution meets a given threshold.

Every problem in APX admits a polynomial-time $\alpha$-constant-factor approximation algorithm for some fixed constant $\alpha$.