Approximation algorithm

From Glossary

Jump to: navigation, search

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.


Views
Personal tools