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!

cc.complexity-theory ds.algorithms approximation-algorithms optimization set-cover 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