Czy złożoność sześcienna jest wciąż aktualna w przypadku LP?

25

Według D. den Hertoga, Podejście punktu wewnętrznego do programowania liniowego, kwadratowego i wypukłego, 1994 , program liniowy z zmiennymi, ograniczeniami i precyzją jest rozwiązywalny w czasie . Czy to zostało poprawione? $n$ $n$ $L$ $O(n^3L)$

cc.complexity-theory reference-request linear-programming

— Aryeh
źródło

Odpowiedzi:

6

Wygląda na to, że KMAnstreicher poprawił wynik do w Anstreicher, Kurt M. „Programowanie liniowe w operacjach O ([n3 / ln n] L)”. SIAM Journal on Optimization 9, no. 4 (1999): 803–812. . Nie czytałem tego artykułu, ale mam nadzieję, że ta odpowiedź pomoże ci w pewnym stopniu. $O((n^3/\ln n)L)$

— strumień
źródło

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.

Licensed under cc by-sa 3.0 with attribution required.