Является ли кубическая сложность все еще современным для LP?

25

Согласно D. den Hertog, «Подход с внутренней точки к линейному, квадратичному и выпуклому программированию», 1994 , линейная программа с переменными, n ограничениями и точностью L разрешима за O ( n 3 L ) времени. Это было улучшено?NNLО(N3L)

Арье
источник

Ответы:

6

О((N3/перN)L)

реактивный самолет
источник