Resumen:
Esta monografía presenta los fundamentos de la Teoría de la Aproximabilidad en problemas NP-duros. Primero, se presentan algunos modelos de computación como las máquinas de Turing y las maquinas RAM, que son luego usados para definir las clases de complejidad P, NP y NPC, con lo cual se da paso al estudio de la aproximabilidad en problemas NP-duros presentando las clases de aproximación APX, PTAS y FPTAS y describiendo dos estrategias muy aplicables en el desarrollo o mejoramiento de algoritmos de aproximación, las estrategias shifting y grid. Además, la presentación de todos los conceptos tratados en esta monografía se ha complementado con ejemplos, tablas y gráficos pertinentes para una mayor facilidad en su comprensión.
