Approximation Algorithm
Un algorithme d'approximation donne une solution quasi-optimale en temps polynomial pour des problèmes NP-hard, garantissant que la qualité est dans un facteur de l'optimum.
Objectif
Fournir des solutions approchées en temps polynomial avec garantie pour les problèmes NP-hard.
Mécanisme
α-approximation : valeur ≤ α*OPT (minimisation) ou ≥ OPT/α (maximisation). Ex : couverture de sommets 2-approx, TSP métrique 1.5-approx (Christofides). PTAS donne (1+ε)-approx pour tout ε.
Cas d’usage
- Approximation NP-hard
- Optimisation combinatoire
- Garanties théoriques