Approximation algorithm

An approximation algorithm is in computer science, an algorithm which solves an optimization problem approximately.

Many optimization problems can be solved with exact algorithms probably will not solve them efficiently. For such problems, it may be useful, at least to find a solution that comes close to an optimal solution.

Quality of approximation algorithms

It is the string associated with an input solution space. For each possible solution is the quality. The goodness of an optimal solution is. An approximation algorithm now searches for a solution, so close as possible to lies.

The quality of an approximation method (so-called approximation ) is determined by the performance of the algorithm. It is defined by the ratio of the approximated solution to the exact solution, measured in an appropriate norm. The performance of a solution is determined by:

This definition of the performance can be applied to both minimization as well as to maximize problems. It always works.

Classes of approximation algorithms

Optimization problems can be distinguished in theoretical computer science in several Approximationsklassen, depending on what level of approximation is possible:

APX

The abbreviation stands for APX approximable and implies that the optimization problem, at least to some degree, is efficiently approximated. One problem is in the class APX if a number and a polynomial algorithm exists that a solution with a performance delivers on every possible input.

PTAS / PAS

PTAS or PAS stands for polynomial time approximation scheme. Unlike the class APX is required here for each that a polynomial algorithm exists that a solution with a performance delivers on every possible input. Thus, the algorithm must be efficient not only for a certain performance, but for every performance, the existential quantifier is replaced by a universal quantifier.

FPTAS

FPTAS stands for fully polynomial time approximation scheme. Here it is required that the algorithm behaves not only polynomial for input, but also on the quality of the approximation. That it thus to each input and each a solution with the performance there, and the algorithm is polynomial in and.

The following applies:

Assuming the above inclusion pictures are genuine inclusions. That is, there are at least, for example, an optimization problem, which is in the class PTAS, but not in the FPTAS class.

Summing up a little further the inclusion chain:

Would mean also that there are optimization problems that are not even in APX. This can be shown by assuming, for example, for the clique problem.