Ein Approximationsalgorithmus liefert für ein Optimierungsproblem in polynomieller Zeit eine Lösung mit garantiertem Abstand zum Optimum.
Beispiel: 2-Approximation für Vertex Cover.