Approximation Algorithm
Un algoritmo de aproximación da una solución casi óptima en tiempo polinomial para problemas NP-hard, garantizando que la calidad está dentro de un factor del óptimo.
Propósito
Proporcionar soluciones aproximadas en tiempo polinomial con garantía para problemas NP-hard.
Mecanismo
α-aproximación: valor ≤ α*OPT (minimización) o ≥ OPT/α (maximización). Ej: cobertura de vértices 2-aprox, TSP métrico 1.5-aprox (Christofides). PTAS da (1+ε)-aprox para cualquier ε.
Casos de uso
- Aproximación NP-hard
- Optimización combinatoria
- Garantías teóricas