ABSTRACT
Let be an NP-hard optimization problem, and let A be an approximation algorithm for . For an instance I of , let A(I ) denote the objective value when running A on I , and let OPT(I ) denote the optimal objective value. The approximation ratio of A for the instance I is RA(I ) = A(I )/OPT(I ), thus, when is minimization (maximization) problem RA(I ) ≥ 1 (RA(I ) ≤ 1).
