Approximation algorithm

Summary

An approximation algorithm is an efficient algorithm for an optimization problem. It returns a solution whose cost is provably within a fixed factor of the optimum. It is the main way to deal with NP-hard optimization problems, where an exact optimum is unlikely to be found in polynomial time. The factor is the approximation ratio. Results on hardness of approximation show that for many problems some ratios cannot be reached unless P equals NP.