Jak nazywa się ten wariant problemu z ustawieniem pokrycia zestawu?

Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli . $U$ $U$ ${\cal F} \subseteq 2^U$ ${\cal F}$ $U$ $\bigcup_{E\in {\cal F}}E=U$

Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełnia ${\cal F}$ ${\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\}$

1) , $\forall E\in {\cal A}, E\in {\cal F}$

2) każdy nowo przybyły ma nowy wkład, tj. , ; $\forall i>1$ $\bigcup_{j=1}^{i-1}E_i \subsetneq \bigcup_{j=1}^{i}E_i$

Problem polega na znalezieniu przyrostowej sekwencji pokrycia o maksymalnej długości (tj. O maksymalnej $|{\cal A}|$ ). Należy zauważyć, że maksymalna długość sekwencji w końcu musi obejmować $U$ , tj $\bigcup_{E\in {\cal A}}E=U$ .

Próbowałem znaleźć algorytm lub algorytm przybliżony, aby znaleźć najdłuższą przyrostową sekwencję pokrycia. Zastanawiałem się tylko, jak znany jest ten wariant problemu z zestawem. Dziękuję Ci!

— Cecha kohomologii
źródło

Potrzebujesz rodziny podzbiorów aby objąć wszechświat ? Ponieważ wtedy oczywiście możesz mieć trudniejszy problem z zestawem okładek, ponieważ szukasz zestawu z dodatkowymi właściwościami. Innymi słowy, zestaw ochrony ogranicza się do twojego problemu. Na wiki set cover znajdują się również wyniki nie do przyjęcia dla set cover.

A

$\cal{A}$

U

$\cal{U}$

— Harry

To tylko spostrzeżenie (zbyt małe, aby dać odpowiedź): kiedy twoje podzbiory mają rozmiar dwa, wtedy to, czego szukasz, to zasadniczo rozciągający się las.

— David Eppstein

Prawdopodobnie nie jest nowy w PO, ale oto kilka uwag. (1) Optymalna wartość wynosi zawsze najwyżej | U |. Czy optymalna wartość jest równa | U | lub nie może być skutecznie ustalony przez chciwy algorytm, który próbuje zminimalizować liczbę elementów objętych. (2) Ten sam zachłanny algorytm działa również, jeśli wszystkie zestawy w F mają rozmiar dwa, patrz komentarz Davida Eppsteina. (3) Ten sam chciwy algorytm nie działa ogólnie (westchnienie). Kontrprzykład: F = {{1,2,3}, {1,4,5,6}, {2,4,5,6}, {3,4,5,6}}.

— Tsuyoshi Ito,

Problem tak naprawdę wcale nie wygląda jak problem z ustawieniem pokrycia ... Bardziej jak hybryda między dopasowaniem a dopasowaniem indukowanym w grafach dwustronnych. Ładnym równoważnym przeformułowaniem jest to, że rodzina jest zła, jeśli żaden element nie jest objęty dokładnie jednym zestawem w rodzinie. Problem polega na znalezieniu największej podrodziny z takiej, że nie ma złej podrodziny.

A

${\cal A}$

F

${\cal F}$

A

${\cal A}$

— daniello

@Neal Young nie jest zły, ponieważ obejmuje dokładnie jeden zestaw (a mianowicie ).

F

${\cal F}$

b

$b$

{a, b}

$\{a,b\}$

— daniello

Odpowiedzi:

Tutaj pokazuję, że problem jest NP-zupełny.

Konwertujemy CNF na wystąpienie problemu w następujący sposób. Załóżmy, że zmiennymi CNF są , a zdania są , gdzie . Niech gdzie wszystkie zestawy w unii są całkowicie rozłączne. W rzeczywistości i , podczas gdy to dowolny zestaw liczności . także i napraw dla każdej rosnącą w środku rodzinę długości , oznaczoną przez dla $n$ $x_i$ $m$ $C_j$ $n<m$ $U=\cup_i (A_i\cup B_i\cup Z_i)$ $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$ $Z_i$ $k=2n+1$ $Z=\cup_i Z_i$ $Z_i$ $k$ $Z_{i,l}$ $l=1..k$ . Dla każdej zmiennej dodajemy zestawów do , każdy zestaw postaci i . Dla każdej klauzuli dodajemy jeden zestaw do , który zawiera , i dla każdego elemencie i dla każdego elemencie . $x_i$ $2k$ $\mathcal F$ $A_i \cup Z_{i,l}$ $B_i \cup Z_{i,l}$ $C_j$ $\mathcal F$ $Z$ $x_i\in C_j$ $\{a_{i,j}\}$ $\bar x_i\in C_j$ $\{b_{i,j}\}$

Załóżmy, że formuła jest zadowalająca, i napraw zadowalające zadanie. Następnie wybierz zestawy postaci lub , w zależności od tego, czy jest prawdziwe, czy nie. Są to zestawy przyrostowe . Teraz dodaj zestawy odpowiadające klauzulom. Te również zwiększają rozmiar, ponieważ klauzule są zadowalające. Wreszcie, możemy nawet dodać więcej zestawów (po jednym dla każdej zmiennej), aby pokrywę sekwencji . $k$ $A_i \cup Z_{i,l}$ $B_i \cup Z_{i,l}$ $x_i$ $nk$ $m$ $k$ $U$

Załóżmy teraz, że zestawy są umieszczone w sekwencji przyrostowej. Należy zauważyć, że co najwyżej zestawy odpowiadające mogą być wybrane dla każdego . Zatem, jeśli nie ma zestawów klauzul w sekwencji przyrostowej, można wybrać najwyżej , co jest za mało. Zauważ, że jak tylko zestaw klauzul zostanie wybrany, możemy wybrać maksymalnie dwa zestawy odpowiadające każdemu , łącznie maksymalnie zestawów. Dlatego musimy wybrać co najmniej zestawów zmiennych, zanim zostanie wybrany dowolny zestaw klauzul. Ale ponieważ możemy wybrać najwyżej dla każdego , oznacza to, że dla każdego wybraliśmy przynajmniej $n(k+1)+m$ $k+1$ $x_i$ $x_i$ $n(k+1)$ $x_i$ $2n$ $n(k-1)$ $k+1$ $x_i$ $1$ , jako . To określa „wartość” zmiennej, dlatego możemy wybierać tylko „prawdziwe” zdania. $k=2n+1$

Aktualizacja: Zmieniono wartość z na jak zauważył Marzio. $k$ $n$ $2n+1$

— domotorp
źródło

Wyjaśnienie: szybko sprawdzana konstrukcję dla unsatisfiable wzorze ( ), ale wydaje się, że można budować sekwencję z zwiększenie zestawy . Prawdopodobnie popełniam błąd: czy mamy ?

x_{1} \land \neg x_{1}

$x_1 \land \neg x_1$

n = k = 1, m = 2

$n=k=1, m=2$

n (k + 1) + m = 4

$n(k+1)+m = 4$

F

$\mathcal F$

F = {{a_{1, 0}, a_{1, 1}, a_{1, 2}, z_{1}}, {b_{1, 0}, b_{1, 1}, b_{1, 2}, z_{1}}, {a_{1, 1}, z_{1}}, {b_{1, 2}, z_{1}}}

$\mathcal F= \{ \{ a_{1,0}, a_{1,1}, a_{1,2}, z_1 \}, \{ b_{1,0}, b_{1,1}, b_{1,2}, z_1\}, \{ a_{1,1}, z_1 \}, \{ b_{1,2}, z_1 \} \}$

— Marzio De Biasi,

Znając ciebie i siebie, jestem pewien, że pomyłka jest moja ... Myślę, że powinniśmy dostać , ale oczywiście to wciąż problem. OK, widzę, gdzie popełniłem błąd, naprawiam go za minutę, dziękuję!

F = {{a_{1, 0}, a_{1, 1}, z_{1}}, {b_{1, 0}, b_{1, 2}, z_{1}}, {a_{1, 1}, z_{1}}, {b_{1, 2}, z_{1}}}

${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1\}, \{b_{1,0},b_{1,2},z_1\},\{a_{1,1},z_1\}, \{b_{1,2},z_1\}\}$

— domotorp

Ok, przyjrzę się jutro! Tylko uwaga, czy możesz napisać (w komentarzu) czym jest dla i jaka jest „wartość docelowa” dla długości sekwencji pokrywającej (czy to k)? Ponieważ w zmodyfikowanej odpowiedzi najpierw ustawiasz , a następnie mów o zestawy są ułożone w sekwencji przyrostowej ; czy to prawda (jeszcze nie próbowałem redukcji)?

F

$\mathcal F$

x_{i} \land \neg x_{i}

$x_i \land \neg x_i$

k = 2 n + 1

$k = 2n+1$

n (k + 1) + m = 2 n^{2} + 2 n + m

$n(k+1)+m = 2n^2+2n + m$

— Marzio De Biasi,

F = {{a_{1, 0}, a_{1, 1}, z_{1},}, {a_{1, 0}, a_{1, 1}, z_{1}, z_{2}}, {a_{1, 0}, a_{1, 1}, z_{1}, z_{2}, z_{3}}, {b_{1, 0}, b_{1, 2}, z_{1}}, {b_{1, 0}, b_{1, 2}, z_{1}, z_{2}}, {b_{1, 0}, b_{1, 2}, z_{1}, z_{2}, z_{3}}, {a_{1, 1}, z_{1}, z_{2}, z_{3}}, {b_{1, 2}, z_{1}, z_{2}, z_{3}}}

${\mathcal F}=\{\{a_{1,0},a_{1,1},z_1,\},\{a_{1,0},a_{1,1},z_1,z_2\},\{a_{1,0},a_{1,1},z_1,z_2,z_3\},\{b_{1,0},b_{1,2},z_1\},\{b_{1,0},b_{1,2},z_1,z_2\},\{b_{1,0},b_{1,2},z_1,z_2,z_3\},\{a_{1,1},z_1,z_2,z_3\},\{b_{1,2},z_1,z_2,z_3\}\}$

— domotorp

Myślę, że jest to poprawne, ponieważ , ale mamy tylko sekwencji przyrostowych.

n (k + 1) + m = 6

$n(k+1)+m=6$

5

$5$

— domotorp

Jest to problem z pakowaniem zestawu pod warunkiem, że dla rozwiązania , dla dowolnego podzbioru , mamy zawsze element w , który jest objęty dokładnie raz. $\mathcal{A}$ $\mathcal{B} \subseteq \mathcal{A}$ $\bigcup_{X \in \mathcal{B}} X$

Dowód: pod warunkiem rozwiązania problemu natychmiast ma tę właściwość. Rzeczywiście, jeśli jest optymalnym rozwiązaniem twojego problemu, to rozważ podzbiór z tych zestawów i że jest ostatnim zestawem w tej sekwencji pojawiającym się w . Z wymaganej właściwości, że rozwiązanie jest przyrostowe, wynika, że obejmuje element, którego nie obejmuje żaden wcześniejszy zestaw, co implikuje powyższą właściwość. $E_1, \ldots, E_m$ $\mathcal{B}$ $E_i$ $\mathcal{B}$ $E_i$

Jeśli chodzi o drugi kierunek, to również łatwe. Zacznij od rozwiązania , znajdź element objęty dokładnie raz, ustaw go jako ostatni zestaw w sekwencji, usuń ten zestaw i powtórz. CO BYŁO DO OKAZANIA. $\mathcal{A}$

To całkiem naturalny problem ...

Szybkie przypomnienie: W problemie pakowania zestawu, biorąc pod uwagę rodzinę zestawów, znajdź maksymalny podzbiór zestawów, które spełniają pewne dodatkowe ograniczenia (powiedzmy, że żaden element nie jest objęty więcej niż 10 razy itp.).

— Sariel Har-Peled
źródło

Czy ta odpowiedź tylko dowodzi, że pytanie jest naturalne, czy jest coś, o co również się twierdzisz?

— domotorp

Mówi to w prostszy sposób. Nie?

— Sariel Har-Peled,

Tak, zgadzam się na to.

— domotorp