Approximationsalgorithmus

Ein Approximationsalgorithmus (oder auch Näherungsalgorithmus) ist in der Informatik ein Algorithmus, der ein Optimierungsproblem näherungsweise löst.

Viele Optimierungsprobleme lassen sich mit exakten Algorithmen vermutlich nicht effizient lösen. Für solche Probleme kann es sinnvoll sein, wenigstens eine Lösung zu finden, die einer optimalen Lösung möglichst nahekommt. Als Maß für die Bewertung von Approximationsalgorithmen benutzt man die sogenannte Güte des Algorithmus.