Approximation algorithm
|
|
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 within 5% of the optimal solution).
NP-hard problems vary greatly in their approximatibility; some, such as the bin-packing problem, can be approximated to arbitrary factors (such approximation algorithms are often called polynomial time approximation schemes or PTAS). Others are impossible to approximate within any constant (or even polynomial) factor (unless P = NP), such as the maximum clique problem.
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.
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 (although it's often possible to conceive optimization versions of such problems, such as the maximum satisfiability problem).
References
- Vijay V. Vazirani. Approximation Algorithms. ISBN 3540653678.
External links
- A compendium of NP optimization problems (http://www.nada.kth.se/~viggo/wwwcompendium/)he:אלגוריתם קירוב