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. ${\displaystyle r}$ ${\displaystyle I}$ ${\displaystyle \leq r}$

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. ${\displaystyle \delta \in (0,1)}$ ${\displaystyle r\leq 1+\delta }$

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 . ${\displaystyle I}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle r\leq 1+1/k}$ ${\displaystyle x}$ ${\displaystyle k}$

The following applies: ${\displaystyle PO\subseteq FPTAS\subseteq PTAS\subseteq APX\subseteq NPO}$

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 . ${\displaystyle P\neq NP}$ ${\displaystyle P\subsetneq NP}$

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 . ${\displaystyle \Pi }$ ${\displaystyle v\colon S(I)\to \mathbb {N} }$ ${\displaystyle I}$ ${\displaystyle p}$ ${\displaystyle opt(I)<p(|I|,maxnr(I))}$ ${\displaystyle I}$ ${\displaystyle \Pi }$ ${\displaystyle \Pi }$ ${\displaystyle opt(I)}$ ${\displaystyle I}$ ${\displaystyle maxnr(I)}$ ${\displaystyle I}$

Since strongly NP-complete problems do not have a pseudopolynomial algorithm (if ), they do not have an FPTAS. ${\displaystyle P\neq NP}$

See also

• Heuristic
• iteration

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