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 efficient
polynomial-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. A typical example for an approximation algorithm is the one for
vertex cover in
graphs: find an uncovered edge and add
both endpoints to the vertex cover, until none remain. It is clear that the resulting cover is at most twice as large as the optimal one. This is a
constant factor approximation algorithm with a factor of 2.