Najszybsza znana złożoność kombinatorycznego algorytmu ILP?

Zastanawiam się, co jest najbardziej znany algorytm, jeśli chodzi o Big- notacji, aby rozwiązać Programowanie Integer Linear? $O$

Wiem, że problem jest , więc nie oczekuję niczego wielomianowego. Wiem, że istnieje wiele heurystyk, które są wykorzystywane w praktycznych zastosowaniach, takich jak CPLEX, ale bardziej interesuje mnie formalna, w najgorszym przypadku złożoność dokładnego algorytmu. $NP$

Niektóre pełnoporcjowych problemy algorytmy w czasie , gdzie , a jest wielomianem. Pokrywa wierzchołków, niezależny zestaw i 3SAT należą do tej kategorii, ale ogólnie SAT i TSP nie (o ile wiemy). $NP$ $O(b^n p(n))$ $1 < b < 2$ $p$

Czy można składać takie oświadczenia dotyczące programowania liczb całkowitych lub poszczególnych pod-instancji?

Jeśli ktoś ma odniesienia do powiązanego problemu związanego z arytmetyką bezpłatnej kalkulatora Presibera, bardzo bym się tym zainteresował.

algorithms complexity-theory reference-request np-complete integer-programming jmite
źródło

Aardal, Karen, Robert Weismantel i Laurence A. Wolsey. „Niestandardowe podejścia do programowania liczb całkowitych.” Discrete Applied Mathematics 123.1 (2002): 5-74. daje wiele referencji. Być może możesz znaleźć odpowiedź, patrząc na nie lub śledząc, co cytują nowsze gazety. Spójrz w szczególności na sekcję 2.

Juho,

Jaka jest różnica między

O ({1.1}^{n})

$O(1.1^{n})$

O (99^{n})

$O(99^{n})$

greybeard

@ Greybeard, niewiele dla P vs NP, ale wiele pod względem realnej podatności na życie, w zależności od stałych, robi to ogromną różnicę.

jmite 18.04.15

Chciałbym mieć nadzieję na wcześniejsze przypomnienie, że biorąc pod uwagę

, różnica w

skutkuje innym zestawem funkcji, podczas gdy jeden w

nie ma i w konsekwencji zostaje wyabstrahowany .

O (b^{n})

$O(b^n)$

O (c n)

$O(cn)$

b

$b$

c

$c$

siwobrody

@jmite Gotowe. Czy miałeś jakieś odniesienie do Ciebie, czy byłeś w stanie znaleźć jakieś nowe informacje?

Juho

Z tego, co mogę stwierdzić na podstawie wyszukiwania, definitywną ankietą wydaje się być:

Aardal, Karen, Robert Weismantel i Laurence A. Wolsey. „Niestandardowe podejścia do programowania liczb całkowitych.” Discrete Applied Mathematics 123.1 (2002): 5-74.

W szczególności sekcja 2.1 omawia programowanie liczb całkowitych w wymiarze ograniczonym i przedstawia algorytmy różnych autorów. Rzeczywiście w ankiecie wymieniono wiele referencji i omówiono niektóre praktyczne wdrożenia.

Dla stałej liczby zmiennych programowanie liniowe liczb całkowitych jest czasem wielomianowym rozwiązanym przez algorytm Lenstry.

Juho
źródło

dobrze, ale jaki jest najszybszy znany algorytm?

dniu

@vzn Nie wiem, to co najwyżej odpowiedź obejmująca „określone pod-instancje”.

Juho,

Najszybsza znana złożoność kombinatorycznego algorytmu ILP?

Odpowiedzi: