Algoritmo de Karmakar

Ideado en su forma arquetípica por el matemático indio Narendra Karmakar, el algoritmo que lleva su nombre ofrece un procedimiento para la resolución de problemas de programación lineal. Cuando en estos problemas se maneja multitud de variables y condiciones de restricción, es común recurrir al auxilio de computadoras para su resolución. El método simplex, ideado por el estadounidense George Dantzig, supuso la aparición de un algoritmo que sirvió de base a un programa informático, gracias al cual se redujo de forma considerable el tiempo de resolución de los problemas. No obstante sus ventajas, el método simplex es de naturaleza exponencial, lo que implica que el tiempo de trabajo que precisa crece exponencialmente, según el tamaño del problema que se ha de resolver. Por ello, muchos matemáticos acometieron la tarea de diseñar algoritmos de tipo polinómico que manejarían un crecimiento del tiempo de resolución potencial, mucho más asequible que el exponencial. Un primer intento en...