Algoritmo de Karmarkar y matrices ralas

Resumen

Este es el segundo de una serie de dos artículos en los que se estudia el método de Karmarkar. Se muestra cómo utilizar la teoría de matrices ralas para obtener una implementación eficiente del proceso de Karmarkar, presentado en el primer artículo. En la fase I del proceso de Karmarkar, se pone en evidencia la forma como se incrementa el tamaño de la matriz de resticciones tecnológicas. La nueva matriz sin embargo, posee una estructura peculiar bastante favorable, debido a la presencia de bloques de ceros que la hacen parte de una familia de matrices bastante conocida, a saber las matrices ralas. Se discute en este trabajo algunas técnicas para manejar este tipo de matrices, y finalmente el autor propone una variante del método del Karmarkar que aprovecha dicha situación.