Según D. den Hertog, Enfoque de punto interior para la programación lineal, cuadrática y convexa, 1994 , un programa lineal con variables, n restricciones y precisión L se puede resolver en el tiempo O ( n 3 L ) . ¿Se ha mejorado eso?
Parece que KMAnstreicher ha mejorado el resultado a en Anstreicher, Kurt M. "Programación lineal en operaciones O ([n3 / ln n] L)". Revista SIAM sobre Optimización 9, no. 4 (1999): 803-812. . No he leído este documento, pero espero que esta respuesta le sea de alguna ayuda.