Están a menudo asociados con problemas NP-hard; como es poco probable que alguna vez se descubran algoritmos eficientes de tiempo polinómico que resuelvan exactamente problemas NP-hard, se opta por encontrar soluciones no-óptimas en tiempo polinomial.
A diferencia de las heurísticas, que usualmente solo encuentran soluciones razonablemente buenas en tiempos razonablemente rápidos, lo que se busca aquí es encontrar soluciones que está demostrado son de calidad y cuyos tiempos de ejecución están acotadas por cotas conocidas.
Idealmente, la aproximación mejora su calidad para factores constantes pequeños (por ejemplo, dentro del 5% de la solución óptima).
Es claro que la cobertura resultante será a lo más dos veces del largo de la solución óptima.
Los problemas NP-hard frecuentemente pueden expresarse como programación entera (PE) y ser resueltos exactamente en tiempo exponencial.
En estos escenarios, se debe competir contra las correspondientes formulaciones de programación entera directa.
, que uno encuentra en todas las posibles instancias del problema.
Del mismo modo, el radio de comportamiento asintótico (asymptotic performance ratio)
es: Es decir, que es el mismo radio de comportamiento absoluto, con una cota inferior
Se utilizan estos dos tipos de radio porque debido a que existen algoritmos donde la diferencia entre ellos es significativa.