APX-hard Decision Problem

Definition

Decision Version of an APX-hard Optimisation Problem

For an APX-hard optimisation problem $\Pi$ with a rational-valued objective, its associated decision problem ${\Pi }_{\mathrm{dec}}$ is:

Instance: an instance $I$ of $\Pi$ and a binary-encoded rational threshold $t$.

Question: does a feasible solution meet the threshold?

$$(I,t)\in {\Pi }_{\mathrm{dec}}⟺\exists S\in {\mathcal{S}}_{\Pi }(I):\{\begin{array}{ll}{f}_{\Pi }(I,S)\le t,& \mathrm{goal}=\min ,\\ f_{\Pi }(I,S)\ge t,& \mathrm{goal}=\max .\end{array}$$

“APX-hard decision problem” is not a standard classification: APX-hardness belongs to the associated optimisation problem and its approximation-preserving reductions. If $\Pi$ is an NP-optimisation problem, this threshold problem belongs to NP; APX-hardness alone does not supply that membership.