Page 135 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

se conoce como método del punto interior, porque justamente realiza eso: no va al óptimo recorrien-
do cada esquina factible de un poliedro (como lo realiza el método Simplex); en lugar de eso, realiza
un camino inteligente en el interior del poliedro.

Pero tal vez el gran avance en los algoritmos de programación lineal no fue la penetración teórica de
Khachiyan o el aprovechamiento novedoso de Karmarkar, sino la fiera competencia entre los algo-
ritmos Simplex y punto interior, lo cual provocó el desarrollo de un código sumamente eficiente para
programación lineal (Dasgupta, Papadimitriou y Vazirani, 2008).

Por último, vale comentar que algunos problemas del tipo NP se pueden reducir a programación
lineal o programación entera. Como ejemplo de ello están el problema SAT y el problema del agente
viajero.

129