Definition
APX Optimisation Problem
An NP-optimisation problem
is an APX optimisation problem if it belongs to the class APX: some polynomial-time algorithm returns a feasible solution within a fixed factor of the optimum on every feasible instance : 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
-constant-factor approximation algorithm for some fixed constant .