Approximation Algorithm
Ein Approximationsalgorithmme liefert in polynomieller Zeit eine nahezu optimale Lösung für NP-schwere Probleme und garantiert, dass die Qualität innerhalb eines Faktors des Optimums liegt.
Zweck
Liefert polynomialzeitliche approximative Lösungen mit Garantie für NP-schwere Probleme.
Mechanismus
α-Approximation: Wert ≤ α*OPT (Minimierung) oder ≥ OPT/α (Maximierung). Bsp: Knotenüberdeckung 2-Approx, metrisches TSP 1.5-Approx (Christofides). PTAS liefert (1+ε)-Approx für beliebiges ε.
Anwendungsfälle
- NP-hard-Approximation
- Kombinatorische Optimierung
- Theoretische Garantien