Algoritmos de aproximación para problemas combinatorios

Se analizan algoritmos heurísticos simples y en tiempo polinómico para encontrar soluciones aproximadas a varios problemas de optimización completos polinómicos, en relación a su comportamiento en el peor de los casos, medido por la relación entre el peor valor de solución que puede ser elegido por el algoritmo y el valor óptimo. Para ciertos problemas, como una forma simple del problema de la mochila y un problema de optimización basado en pruebas de satisfactibilidad, existen algoritmos para los cuales esta relación está acotada por una constante, independiente del tamaño del problema. Para varios problemas de cobertura de conjuntos, algoritmos simples producen relaciones en el peor de los casos que pueden crecer con el logaritmo del tamaño del problema. Y para el problema de encontrar el cliques máximo en un grafo, no se ha encontrado ningún algoritmo para el cual la relación no crezca al menos tan rápido como 0(nε), donde n es el tamaño del problema y ε > 0 depende del algoritmo.