APPROXIMATION ALGORITHM

Approximation algorithm - This reaches a feasible solution to an NP-complete problem in polynomial time with a guaranteed bound on the quality of the solution. For minimization, with Z* = optimal value > 0, the bound generally has the form:

Z <= rZ* for some r > 1, where Z is the value of the feasible solution.