APX-complete Optimisation Problem

Definition

APX-complete Optimisation Problem

An optimisation problem $\Pi$ is APX-complete if it is both an APX optimisation problem and APX-hard, using the same PTAS-reduction convention:

$$\Pi \in \mathrm{APX}\wedge \forall \Gamma \in \mathrm{APX}:\Gamma {\le }_{\mathrm{PTAS}}\Pi .$$

It admits a polynomial-time constant-factor approximation, but no PTAS unless P = NP. Its decision version asks whether a feasible solution meets a given threshold.