| • Science | • People | • Locations | • Timeline |
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 .
Another limitation of the approach is that it applies only to optimization problems and not to “pure” decision problems like Satisfiability.