Approximation Algorithms and Approximation Ratio

For an NP-hard optimization problem, a polynomial-time rho-approximation guarantees a solution within a factor rho of the optimum; the ratio is a monotone worst-case bound (factor c gives every c' >= c for free) and is defined only for optimization, never for decision, problems.