Algoritmo exacto

En informática e investigación de operaciones , los algoritmos exactos son algoritmos que siempre resuelven un problema de optimización de manera óptima.

A menos que P = NP , un algoritmo exacto para un problema de optimización NP-hard no puede ejecutarse en el tiempo polinomial del peor caso . Se han realizado investigaciones exhaustivas para encontrar algoritmos exactos cuyo tiempo de ejecución sea exponencial con una base baja. ^{[1] [2]}

Véase también

• Reducción que preserva la aproximación
• APX es la clase de problemas con algún algoritmo de aproximación de factor constante.
• Algoritmo heurístico
• PTAS : un tipo de algoritmo de aproximación que toma la relación de aproximación como parámetro

Referencias

1. Fomin, Fedor V.; Kaski, Petteri (marzo de 2013), "Algoritmos exponenciales exactos", Communications of the ACM , 56 (3): 80–88, doi :10.1145/2428556.2428575.
2. Fomin, Fedor V.; Kratsch, Dieter (2010). Algoritmos exponenciales exactos . Saltador. pag. 203.ISBN​ 978-3-642-16532-0.