Algorytmy pakowania zestawu

Wydaje się, że w przypadku niektórych problemów NP-trudnych jest dużo pracy nad opracowaniem szybkich algorytmów dokładnych w czasie wykładniczym (tj. Wyniki postaci: Algorytm A rozwiązuje problem w czasie O (c ^ n), przy c małym). Wydaje się, że jest sporo pracy w związku z niektórymi problemami trudnymi dla NP (np. Zmierz i pokonaj: prosty algorytm niezależnego zestawu O ( 2 0,288 n ) . SODA'06 ), ale nie udało mi się znaleźć podobna praca dla problemu pakowania zestawu. Wydaje się, że istnieją podobne prace nad niektórymi ograniczeniami problemu pakowania zestawu (np. An O ∗ ( 3,523 k$x$$O(2^{0.288n})$$O^{*}(3.523^{k})$ Sparametryzowany algorytm dla pakowania 3-zestawowego), ale nie znalazłem żadnego dla ogólnego problemu z pakowaniem zestawu.

Więc moje pytanie brzmi: jaka jest najlepsza złożoność czasu na dokładne rozwiązanie problemu ważenia upakowania zestawu, w którym istnieje zestawów zaczerpniętych ze świata n elementów?$m$$n$

Interesuje mnie również związek między liczbą zestawów a wielkością wszechświata. Na przykład, czy była praca algorytmiczna w sytuacjach, w których jest względnie duże w porównaniu do n (tj. Blisko 2 n )?$m$$n$$2^n$

Rzeczywiście, zestaw pakowania, partycjonowanie i przykrycie zostały zbadane pod kątem dokładnych czasów działania algorytmu. Aby odpowiedzieć na twoje ostatnie pytanie, możesz rozwiązać pakowanie zestawów ważonych w czasie programując dynamicznie we wszystkich podzbiorach [ n ] . Co więcej, jeśli twoje liczby całkowite są ograniczone przez M , możesz rozwiązać je w czasie O ( M 2 n ) , nawet jeśli m jest tak duże jak 2 n , patrz$O(m2^n)$$[n]$$M$$O(M2^n)$$m$$2^n$

http://dx.doi.org/10.1137/070683933

BTW, Sparametryzowany wynik dla zestawów nie jest najlepiej znany, patrz$3$

http://arxiv.org/abs/1007.1161

za najnowocześniejszy algorytm i listę poprzednich wyników problemu.

$O(2^{0.288n})$