# Approximation algorithm

In computer science, an **approximation algorithm** (or **approximation algorithm** ) is an algorithm that approximately solves an optimization problem .

Many optimization problems can probably not be solved efficiently with exact algorithms . For such problems it can make sense to find at least one solution that comes as close as possible to an optimal solution. The so-called quality of the algorithm is used as a measure for the evaluation of approximation algorithms .

## Classes of approximation algorithms

In theoretical computer science, optimization problems are divided into different approximation classes, depending on which degree of approximation is possible:

### APX

The abbreviation *APX* stands for * ap pro x imable* and indicates that the optimization problem can be approximated efficiently, at least to a certain extent. A problem lies in the class

*APX*when a number and a polynomial algorithm that delivers a solution with a quality for every admissible input exist.

### PTAS / PAS

*PTAS* or *PAS* stands for * p olynomial t ime a pproximation s cheme* . In contrast to the class

*APX*, it is required here for each that a polynomial algorithm exists that delivers a solution with a quality for every permissible input . The algorithm must therefore not only be efficient for a certain quality, but for every approximation quality.

### FPTAS

*FPTAS* stands for * f ully p olynomial t ime a pproximation s Cheme* . Here it is required that the algorithm behave not only polynomially to the input, but also to the quality of the approximation; That it outputs a solution with the quality for each input and each and that its running time is polynomial in and .

The following applies:

Assuming the above inclusion maps are true inclusions. This means that there is, for example, at least one optimization problem that is in the *PTAS* class but not in the *FPTAS* class . Under this assumption, there is also at least one optimization problem that is not in *APX* . This can be shown under the assumption for the clique problem , for example .

Let be an optimization problem whose objective function is integer for all instances . If there is a polynomial with for each instance , then it follows from the existence of an FPTAS for the existence of a pseudopolynomial algorithm for . Here the optimal solution for the instance and the maximum value of a variable is of .

Since strongly NP-complete problems do not have a pseudopolynomial algorithm (if ), they do not have an FPTAS.

## See also

## literature

- Rolf Wanka:
*Approximation Algorithms - An Introduction*, Teubner, Wiesbaden, 2006, ISBN 3-519-00444-5 - Klaus Jansen, Marian Margraf:
*Approximate Algorithms and Non-Approximatability*, de Gruyter, Berlin, New York, 2008, ISBN 978-3-11-020316-5