Approximation algorithm

In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems.


Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficientpolynomial time exact algorithms solving NP-hard problems, one settles for polynomial time sub-optimal solutions. 


Unlike heuristics, which usually only find reasonably good solutions reasonably fast, one wants provable solution quality and provable run time bounds. Ideally, the approximation is optimal up to a small constant factor (for instance within 5% of the optimal solution). 


Approximation algorithms are increasingly being used for problems where exact polynomial-time algorithms are known but are too expensive due to the input size.

Cited From Wikipeida