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 in graphs: 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(n²⁰⁰⁰).

Another limitation of the approach is that it applies only to optimization problems and not to “pure” decision problems like Satisfiability.

References

• Approximation Algorithms by Vijay V. Vazirani

External links

• A compendium of NP optimization problems