Pakowanie zestawu - Set packing

Pakowanie zbiorów jest klasycznym problemem NP-zupełnym w obliczeniowej teorii złożoności i kombinatoryce i było jednym z 21 problemów NP-zupełnych Karpa .

Załóżmy, że ktoś ma skończony zbiór S oraz listę podzbiorów w S . Następnie problem pakowania zestawów pyta, czy niektóre k podzbiorów na liście są rozłączne parami (innymi słowy, żadne dwa z nich nie mają wspólnego elementu).

Bardziej formalnie, biorąc pod uwagę wszechświat i rodzinę podzbiorów , opakowanie jest podrodziną zbiorów, w których wszystkie zestawy są rozłączne parami. Rozmiar opakowania to . W zadaniu decyzyjnym o zbiorze pakietów wejściowych jest para i liczba całkowita ; pytanie brzmi, czy istnieje zestaw opakowań o rozmiarze lub większym. W przypadku problemu optymalizacji upakowania zestawu dane wejściowe to para , a zadaniem jest znalezienie zestawu upakowania, który wykorzystuje najwięcej zestawów. ${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {S}}}$${\ displaystyle {\ mathcal {U}}}$${\ displaystyle {\ mathcal {C}} \ subseteq {\ mathcal {S}}}$${\ displaystyle {\ mathcal {C}}}$${\ displaystyle | {\ mathcal {C}} |}$${\ Displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}$${\ displaystyle k}$${\ displaystyle k}$${\ Displaystyle ({\ mathcal {U}}, {\ mathcal {S}})}$

Problem jest wyraźnie w NP, ponieważ mając k podzbiorów, możemy łatwo zweryfikować, że są one rozłączne parami w czasie wielomianowym .

Wersja optymalizacja problemu, maksymalnej ustawionej pakowania , prosi o maksymalna ilość zbiorów parami rozłącznych na liście. Jest to problem maksymalizacyjny, który można naturalnie sformułować jako program liniowy z liczbą całkowitą , należący do klasy problemów pakowania .

Pary problematyczne przykrywanie / pakowanie
Pokrywanie problemów Problemy z pakowaniem Minimalne pokrycie zestawu Maksymalne upakowanie zestawu Minimalne pokrycie krawędzi Maksymalne dopasowanie Minimalne pokrycie wierzchołków Maksymalny niezależny zestaw Pokrycie kosza Pakowanie pojemników Pokrycie wielokątów Pakowanie prostokątne
v t mi

Sformułowanie programu liniowego w postaci liczb całkowitych

Maksymalny problem upakowania zestawu można sformułować jako następujący program liniowy w postaci liczb całkowitych .

Wyolbrzymiać	${\ displaystyle \ sum _ {S \ in {\ mathcal {S}}} x_ {S}}$		(zmaksymalizuj całkowitą liczbę podzbiorów)
z zastrzeżeniem	${\ Displaystyle \ sum _ {S \ dwukropek e \ w S} x_ {S} \ leqslant 1}$	dla wszystkich ${\ displaystyle e \ in {\ mathcal {U}}}$	(wybrane zestawy muszą być rozłączne parami)
	${\ displaystyle x_ {S} \ in \ {0,1 \}}$	dla wszystkich . ${\ displaystyle S \ in {\ mathcal {S}}}$	(każdy zestaw jest w opakowaniu lub nie)

Złożoność

Problem upakowania zestawu jest nie tylko NP-kompletny, ale jego wersja optymalizacyjna (ogólny problem maksymalnego upakowania zestawu) okazała się równie trudna do przybliżenia, jak problem maksymalnej kliki ; w szczególności nie można jej aproksymować w ramach żadnego stałego współczynnika. Najbardziej znany algorytm aproksymuje go w ramach współczynnika . Wariant ważony również może być przybliżony. ${\ Displaystyle O ({\ sqrt {| U |}})}$

Jednak problem ma wariant, który jest łatwiejszy do rozwiązania: jeśli założymy, że żaden podzbiór nie przekracza k ≥3 elementów, odpowiedź można przybliżyć w ramach współczynnika k / 2 + ε dla dowolnego ε> 0; w szczególności problem z zestawami 3-elementowymi można oszacować w przybliżeniu w około 50%. W innym, łatwiejszym wariancie, jeśli żaden element nie występuje w więcej niż k podzbiorów, odpowiedź można przybliżyć w ramach współczynnika k . Dotyczy to również wersji ważonej.

Równoważne problemy

Istnieje redukcja czasu wielomianu jeden do jednego między problemem zestawu niezależnego a problemem pakowania zestawu:

• Biorąc pod uwagę problem z pakowaniem zestawu w kolekcji , utwórz wykres, na którym dla każdego zestawu znajduje się wierzchołek , a pomiędzy i jeśli jest krawędź . Teraz każdy niezależny zestaw wierzchołków w wygenerowanym wykresie odpowiada zestawowi pakowania w . ${\ displaystyle {\ mathcal {S}}}$${\ displaystyle S \ in {\ mathcal {S}}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {S}}$${\ displaystyle v_ {T}}$${\ displaystyle S \ cap T \ neq \ varnothing}$${\ displaystyle {\ mathcal {S}}}$
• Biorąc pod uwagę niezależne zadanie zestawu wierzchołków na wykresie , utwórz zbiór zestawów, w których dla każdego wierzchołka istnieje zestaw zawierający wszystkie sąsiadujące krawędzie . Teraz każde opakowanie zestawu w wygenerowanej kolekcji odpowiada niezależnemu wierzchołkowi ustawionemu w . ${\ Displaystyle G (V, E)}$${\ displaystyle v}$${\ displaystyle S_ {v}}$${\ displaystyle v}$${\ Displaystyle G (V, E)}$

Jest to również dwukierunkowa redukcja PTAS i pokazuje, że te dwa problemy są równie trudne do przybliżenia.

Przypadki specjalne

Dopasowanie i dopasowanie trójwymiarowe to szczególne przypadki pakowania zestawu. Dopasowanie maksymalnego rozmiaru można znaleźć w czasie wielomianowym, ale znalezienie największego dopasowania trójwymiarowego lub największego zestawu niezależnego jest NP-trudne.

Inne powiązane problemy

Pakowanie zestawu jest jednym z rodziny problemów związanych z przykryciem lub podziałem elementów zestawu. Jednym ze ściśle powiązanych problemów jest problem z ustawioną okładką . Tutaj jesteśmy również otrzymuje zestaw S oraz listę zestawów, ale głównym celem jest ustalenie, czy możemy wybrać k zestawów, które łącznie zawierają każdy element S . Te zestawy mogą się pokrywać. Wersja optymalizacyjna znajduje minimalną liczbę takich zestawów. Maksymalne upakowanie zestawu nie musi obejmować każdego możliwego elementu.

Z drugiej strony, problem dokładnego pokrycia NP-zupełnego wymaga, aby każdy element znajdował się dokładnie w jednym z podzbiorów. Znalezienie w ogóle takiej dokładnej okładki, niezależnie od rozmiaru, to problem NP-zupełny . Jeśli jednak utworzymy pojedynczy zestaw dla każdego elementu S i dodamy go do listy, wynikowy problem jest tak prosty, jak pakowanie zestawu.

Karp pierwotnie wykazał pakowanie zestawu NP-kompletne poprzez redukcję problemu klikowego .

Zobacz także: Pakowanie w hipergraf .

Uwagi

Bibliografia

• Maksymalne pakowanie zestawu , Viggo Kann.
• „ pakowanie zestawu ”. Słownik algorytmów i struktur danych , redaktor Paul E. Black, National Institute of Standards and Technology. Zwróć uwagę, że definicja tutaj jest nieco inna.
• Steven S. Skiena. „ Ustaw pakowanie ”. Podręcznik projektowania algorytmów .
• Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski i Gerhard Woeginger . „ Maksymalne pakowanie zestawu ”. Kompendium problemów optymalizacji NP . Ostatnia modyfikacja 20 marca 2000 r.
• Michael R. Garey i David S. Johnson (1979). Komputery i trudność: przewodnik po teorii kompletności NP . WH Freeman. ISBN   978-0-7167-1045-5 . A3.1: SP3, str. 221.
• Vazirani, Vijay V. (2001). Algorytmy aproksymacyjne . Springer-Verlag. ISBN   978-3-540-65367-7 .

Linki zewnętrzne

• [1] : Program Pascal do rozwiązania problemu. From Discrete Optimization Algorithms with Pascal Programs , MacIej M. Syslo, ISBN   0-13-215509-5 .
• Testy porównawcze z ukrytymi optymalnymi rozwiązaniami do pokrywania zestawu, pakowania zestawu i określania zwycięzcy
• Rozwiązywanie problemu pakowania w PHP
• Optymalizacja trójwymiarowego pakowania pojemników