An approximation algorithm is an algorithm for solving an optimization problem that runs in polynomial time in the length of the input and outputs a solution that is guaranteed to be close to the optimal solution. "Close" has some well-defined sense called the performance guarantee.

Approximation algorithms are different from relaxations in the sense that they operate on the entire original problem and the solution they produce is therefore feasible for the original problem. They can, however, be used as relaxations in methods like branch and bound, since they do provide the same type of information that a relaxation is typically required to provide, namely a bound on the value of the objective function.

An area in optimization related to approximation algorithms is local search. There is, however, a major distinction between the two, which is that local search does not provide a guarantee on the quality of the solution. Local search heuristics stop short of being approximation algorithms, but often in practice they provide much better solutions.