A class of algorithms that finds near-optimal solutions instead of optimal solutions.
They can often used for problems that are NP-complete or when it is feasible to trade optimality for running time.
These algorithms are often evaluated based on their Approximation Ratio. If an algorithm achieves an approximation ratio of , it is called a -approximation algorithm.
If an approximation algorithm is randomised then its Approximation Ratio is calculated using the expected cost. If such an algorithm attains an approximation ratio of it is called a randomised -approximation algorithm.
A more sophisticated version of an approximation algorithm that allows user to control the trade-off between Approximation Ratio and running time are described as Approximation Schemes.