Güte von Approximationsalgorithm

Einfache Sprache

Die Güte eines Approximativen Algorithmus setzt die approximierte Lösung $x$ mit der optimalen Lösung $x_\textrm{OPT}$ in Bezug. Dabei entsteht ein Faktor $r$ der Beschreibt um wie viel großer bzw. kleiner $x$ ist, anhängig davon ob es sich um eine Maximierungsaufgabe ($rx = x_\textrm{OPT}$) bzw. Minimierungsaufgabe ($\frac{1}{r}x = x_\textrm{OPT}$)handelt, mit $r\geq 1$.