# Approximation algorithm

An algorithm that 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 $LaTeX: Z^*$ being a positive optimal value, the bound generally has the form:
$LaTeX: Z \le rZ^* \mbox{ for some } r > 1,$
where $LaTeX: Z$ is the value of the feasible solution.