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 . 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 $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 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 (tj. Blisko )? $m$ $n$ $2^n$

ds.algorithms

— Travis Service
źródło

Google ? „zestaw do pakowania”? en.wikipedia.org/wiki/Set_packing nie jest to jeszcze pytanie na poziomie badawczym (zobacz nasze FAQ). Zamknięcie teraz ...

— Suresh Venkat,

@ Suresh, interesują mnie wyniki formularza: Algorytm A rozwiązuje problem ustawiania upakowania w czasie O (c ^ n), przy czym c jest małe. Jest taka praca dla innych problemów trudnych dla NP (np. Zmierz i pokonaj: prosty algorytm zbioru niezależnego od O (2 ^ 0,288n). SODA'06). Artykuł w Wikipedii, który linkujesz, nie omawia tego i nie znalazłem żadnych najnowszych artykułów omawiających złożoność czasową pakowania zestawu. Większość pracy, którą znalazłem, dotyczy problemu pakowania k-setów. To pytanie typu „prośba o referencję”. Czy tego rodzaju pytania są tu mile widziane? a może pytanie nie zostało napisane wystarczająco dobrze?

— Travis Service,

To faktycznie ma o wiele więcej sensu. kluczową kwestią jest to, że szukasz algorytmów DOKŁADNYCH dla ważonego pakowania zestawu. Jeśli chcesz przeredagować, podać wszelkie odniesienia do pakowania

set (a także tego, co to jest), chętnie otworzę ponownie - po prostu oflaguj to dla uwagi moderatora.

k

$k$

— Suresh Venkat,

Popierałbym ponowne otwarcie tego pytania. „Złożoność czasu” zwykle odnosi się do dokładnych algorytmów, chyba że podano inaczej, nie?

— arnab

To pytanie powinno zostać ponownie otwarte.

— Peter Shor,

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 . Co więcej, jeśli twoje liczby całkowite są ograniczone przez , możesz rozwiązać je w czasie , nawet jeśli jest tak duże jak , 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.

— Andreas Björklund
źródło