From Wikipedia, the free encyclopedia.
In computer science, approximation algorithms are
an approach to attacking NP-hard optimization problems. Since it is unlikely that
there can ever be efficient exact algorithms solving NP-hard problems, one settles for non-optimal solutions, but requires them
to be found in polynomial time. Unlike heuristics, which just usually find reasonable 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 (say 5%).
NP-hard problems vary greatly in their approximatibility; some can be approximated to arbitrary factors (such approximation
algorithms are often called polynomial time approximation schemes or PTAS), some can essentially not be
approximated at all.
A typical example for an approximation algorithm is the one for Vertex Cover: Find an uncovered edge and take both end points into the vertex cover. Clearly,
this can only yield a set up to two times larger than the optimal one.
Frequently, one can gain approximation algorithms from examining relaxed linear programs.
Not all approximation algorithms are suitable for practical application. For example, most people would not be impressed by a
scheme which provably will require them to spend less than twenty times the money that is minimally needed. Also, for some
approximation algorithms, the polynomial run time can be quite bad, like O(n2000).
Another limitation of the approach is that it applies only to optimization problems and not to “pure” decision
problems like Satisfiability.