Approximationsalgorithmen lösen schwere Optimierungsprobleme nicht exakt, sondern mit einer beweisbaren Gütegarantie: Sie liefern eine Lösung, die garantiert nur einen festen Faktor vom Optimum entfernt liegt. Sie sind die wissenschaftlich saubere Antwort auf NP-vollständige Probleme, für die P vs. NP bis heute keine Polynomialzeit-Lösung kennt.
Der Approximationsfaktor
Ein Faktor-ρ-Algorithmus garantiert: Bei Minimierung ist das Ergebnis höchstens ρ-mal so groß wie das Optimum, bei Maximierung mindestens 1/ρ des Optimums. Der Faktor wird oft in der Big-O-Notation bzw. als Konstante angegeben — ein Faktor 2 bedeutet also maximal doppelt so schlecht wie optimal. Die Garantie ist der entscheidende Unterschied zur Heuristik: Deren Ergebnisse können beliebig weit vom Optimum abweichen, ein Approximationsalgorithmus hat eine beweisbare Schranke.
Klassische Beispiele
- Vertex Cover: Ein maximales Matching liefert eine 2-Approximation.
- TSP in metrischen Graphen: Der Christofides-Algorithmus erreicht Faktor 3/2.
- Rucksackproblem: Approximationsschemata (PTAS) erreichen Faktor 1+ε in Polynomialzeit.
- Set Cover: Greedy-Wahl erreicht eine ln(n)-Approximation.
Denkweisen wie Greedy, Backtracking und dynamische Programmierung liefern oft die Bausteine; formal zeigt man die Güte meist per Reduktion und Argumenten über Struktur und Aussagenlogik-artige Bedingungen der Instanz. Auch praxisnahe Zuordnungen wie das Assignment-Problem bekommen Approximationsvarianten, wenn die exakten Verfahren zu teuer werden.