Złożoność obliczeniowa/Wykład 8: Schematy aproksymacji i klasa MAXSNP

<flashwrap>file=ZO-8-1.swf|size=small</flashwrap>

<div.thumbcaption>Rysunek 8.1.

<flash>file=ZO-8-2.swf|width=300|height=200</flash>

<div.thumbcaption>Rysunek 8.2.

Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki

Wprowadzenie

Na poprzednim wykładzie zajmowaliśmy się algorytmami aproksymacyjnymi dla przykładowych trudnych problemów optymalizacyjnych. Dla większości z tych algorytmów udawało nam się podać gwarancję dokładności za pomocą stałego współczynnika efektywności przybliżenia.

W tym module postawimy sobie znacznie ambitniejsze zadanie - będziemy szukać algorytmów, którym na wejściu ustala się dopuszczalny błąd przybliżenia rozwiązania optymalnego. Pokażemy problemy, dla których jest możliwa taka "dowolnie dokładna" aproksymacja.

W drugiej części poznamy klasę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} - jest to bardzo szeroka i interesująca klasa problemów optymalizacyjnych, a pytanie o to, czy należące do niej problemy mogą być dowolnie dobrze aproksymowane było bardzo istotnym zagadnieniem teorii algorytmów aproksymacyjnych. Odpowiedź na to pytanie poznamy dopiero w następnym module.

Schematy aproksymacji

Żeby wyrazić te nowe oczekiwania potrzebujemy nowych notacji:

Definicja

Mówimy, że algorytm ${𝒜}$ jest {schematem aproksymacji} dla problemu Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -optymalizacyjnego $\mathrm{\Pi }$, jeżeli dla wejścia Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{I,\epsilon}} , gdzie $I$ jest instancją problemu $\mathrm{\Pi }$, a $ϵ>0$ opisuje dopuszczalny błąd, znajduje rozwiązanie takie, że:

• Parser nie mógł rozpoznać (nieznana funkcja „\obj”): {\displaystyle \displaystyle \obj_\Pi(I,{ \mathcal{A}(I,\epsilon) }) \leq \braq{1 + \epsilon} \opt_\Pi(I) } dla problemu minimalizacji.
• Parser nie mógł rozpoznać (nieznana funkcja „\obj”): {\displaystyle \displaystyle \obj_\Pi(I,{ \mathcal{A}(I,\epsilon) }) \geq \braq{1 - \epsilon} \opt_\Pi(I) } dla problemu maksymalizacji.

Definicja

Jeśli dla dowolnego $ϵ>0$ czas działania ${𝒜}$ na wejściu Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{I,\epsilon}} jest wielomianowy względem Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{I}} , to ${𝒜}$ jest {wielomianowym schematem aproksymacji}. Będziemy używać skróconej notacji PTAS (od polynomial time approximation scheme) dla oznaczenia tego faktu.

Zauważmy, że w tej definicji wymagamy wielomianowego czasu działania tylko względem rozmiaru instancji przy ustalonym dopuszczalnym błędzie. Oznacza to, że czas działania może być nawet wykładniczy względem wartości parametru $ϵ$. Nie jest to sytuacja komfortowa. Możemy w związku z tym wzmocnić wymagania postawione dla algorytmu.

Definicja

Jeżeli czas działania algorytmu ${𝒜}$ jest wielomianowy względem Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{I}} oraz wartości $\frac{1}{ϵ}$, to ${𝒜}$ jest {w pełni wielomianowym schematem aproksymacji}. Omawiając takie algorytmy będziemy używać notacji FPTAS (fully polynomial time approximation scheme).

Ćwiczenie

{{{3}}}

Schemat aproksymacji dla problemu KNAPSACK

Pokazaliśmy, że nie warto szukać algorytmów FPTAS dla problemów silnie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełnych. Rozpoczniemy w związku z tym dalsze poszukiwania schematów aproksymacyjnych od przyjrzenia się raz jeszcze problemowi plecakowemu. Wiemy, że nie jest to problem silnie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełny i znamy dla niego algorytm pseudowielomianowy. Bardzo często istnienie algorytmu pseudowielomianowego można wykorzystać przy konstrukcjii schematów aproksymacji. Zobaczymy teraz klasyczną konstrukcję opartą o ten pomysł.

Pokażemy teraz algorytm pseudowielomianowemu rozwiązujący problem KNAPSACK. Poznaliśmy już jeden taki alorytm, ale tamten nie nadaje się do konstrukcji schematu aproksymacji.

Algorytm pseudowielomianowy dla problemu plecakowego.

1. Oblicz $V=\underset{i=1,2,\dots ,n}{\max }v(a_i)$.
2. Oblicz $W_{i,u}$ określone dla $0\le i\le n$ i $0\le u\le nV$ jako "minimalny sumaryczny rozmiar podzbioru przedmiotów $S\subseteq a_1,a_2,\dots ,a_i$ taki że sumaryczna wartość tych przedmiotów wynosi dokładnie $u$". Obliczenia można dokonać metodą dynamiczną korzystając z następujących własności rekurencyjnych:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned W_{0,u} &= \infty \\ W_{i+1,u} &= \min(W_{i,u},W_{i,u- v(a_{i+1}) }+ w(a_{i+1}) ) \endaligned}

1. Odczytaj rozwiązanie z wartości $W$.

Algorytm ten można zakodować tak, aby znajdował optymalne rozwiązanie w czasie Parser nie mógł rozpoznać (nieznana funkcja „\notO”): {\displaystyle \displaystyle \notO{n^2V}} . Szczegóły implementacji pozostawiamy jako ćwiczenie.

Zauważmy, że gdyby wartości przedmiotów były ograniczone przez wielomianową funkcję $n$, to skonstruowany algorytm byłby wielomianowy. To jest podstawą schematu aproksymacji, który będzie zaokrąglał wartości przedmiotów tak, aby były one wielomianowe względem $n$ i $\frac{1}{ϵ}$. Oto algorytm:

Algorytm zaokrągleniowy.

1. Oblicz $K=\frac{ϵV}{n}$.
2. Dla każdego przedmiotu oblicz Parser nie mógł rozpoznać (nieznana funkcja „\floor”): {\displaystyle \displaystyle v'(a_i) = \floor{\frac{ v(a_i) }{K}}} .
3. Używając algorytmu pseudowielomianowego rozwiąż problem z wartościami $v^{\prime }$.

Twierdzenie

Algorytm zaokrągleniowy jest FPTAS dla problemu plecakowego.

Dowód

Musimy pokazać, że dla zbioru $S$ znajdowanego przez algorytm zachodzi:

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \sum_{i \in S} v(a_i) \geq \braq{1 - \epsilon} \opt }

Niech $O$ będzie rozwiązaniem optymalnym. Możemy wtedy zapisać ciąg nierówności:

Parser nie mógł rozpoznać (nieznana funkcja „\floor”): {\displaystyle \displaystyle \sum_{i \in S} v(a_i) \geq \sum_{i \in S} \floor{\frac{ v(a_i) }{K}} K \geq \sum_{i \in O} \floor{\frac{ v(a_i) }{K}} K \geq \sum_{i \in O} \braq{ v(a_i) - K} \geq \sum_{i \in O} v(a_i) - nK }

Korzystamy po kolei z własności zaokrąglenia, optymalności rozwiązania $S$ przy wartościach wydzielonych przez $K$, własności zaokrąglenia i tego, że Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{S} \leq n} .

Udowodniliśmy, że wartość rozwiązania znajdowanego przez algorytm jest nie mniejsze niż Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt - nK = \opt - \epsilon V \geq \braq{1-\epsilon} \opt} . Jest to zatem schemat aproksymacyjny. Musimy jeszcze oszacować czas działania algorytmu. Wynosi on Parser nie mógł rozpoznać (nieznana funkcja „\notO”): {\displaystyle \displaystyle \notO{n^2\floor{\frac{V}{K}}} = \notO{n^2\floor{\frac{n}{\epsilon}}}} , a więc jest wielomianowy zarówno względem $n$, jak i $\frac{1}{ϵ}$.

Ćwiczenie

{{{3}}}

Asymptotyczny PTAS dla BIN PACKING

Pokazaliśmy, że problem plecakowy może być aproksymowalny z dowolną dokładnością w czasie wielomianowo zależnym od wielkości danych i dopuszczalnego błędu. Dla problemuu pakowania nie możemy się spodziewać równie dobrych wyników. Jest to problem silnie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełny i o ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to nie może istnieć FPTAS. Pokazaliśmy również, że nie ma algorytmu osiągającego stałą aproksymacji mniejszą od $\frac{3}{2}$. Dowód opierał się o fakt, że o ile Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{P} \neq \cc{NP}} , to nie da się efektywnie sprawdzać, czy da się przedmioty upakować do dwóch pojemników.

Instancje, które zabraniały aproksymacji lepszej niż $\frac{3}{2}$ miały ograniczoną wartość optimum. Skonstruujemy teraz asymptotyczny PTAS dla problemu pakowania, który może osiągać dowolnie dobrą aproksymację ale dla odpowiednio dużych wartości optimum.

Precyzując, podamy rodzinę algorytmów ${{𝒜}}_{ϵ}$ dla $0<ϵ\le \frac{1}{2}$ działających w czasie wielomianowym od liczby przedmiotów i znajdujących rozwiązanie używające co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{1 + 2\epsilon}\opt + 1} pojemników.

Zanim będziemy mogli przedstawić algorytmy ${{𝒜}}_{ϵ}$ musimy pokazać dwa pomocnicze lematy, które pokazują rozwiązania dla pewnych uproszczonych instancji problemu.

Lemat

Dla dowolnego $ϵ>0$ oraz liczby całkowitej $K$ istnieje algorytm wielomianowy rozwiązujący problem pakowania dla instancji, w których występują przedmioty o co najwyżej $K$ różnych rozmiarach, z których każdy jest nie mniejszy niż $ϵ$.

Dowód

Liczba przedmiotów w jednym pojemniku jest ograniczona przez Parser nie mógł rozpoznać (nieznana funkcja „\floor”): {\displaystyle \displaystyle M=\floor{\frac{1}{\epsilon}}} . Suma rozmiarów większej liczby przedmiotów musi przekraczać $1$, gdyż każdy z nich ma rozmiar nie mniejszy niż $ϵ$.

Liczba możliwych zawartości jednego pojemnika jest zatem ograniczona przez $R=(\genfrac{}{}{0ex}{}{M+K}{M})$. Ograniczenie to uzyskujemy, gdyż jest to liczba $M$-elementowych multipodzbiorów zbioru $K$-elementowego. Zauważmy, że liczb $R$ jest stałą zależną tylko od $K$ i $ϵ$.

Liczba pojemników w rozwiązaniu jest ograniczona w oczywisty sposób przez $n$. Zatem liczba możliwych rozwiązań dopuszczalnych jest ograniczona przez $P=(\genfrac{}{}{0ex}{}{n+R}{R})$. Tym razem jest to liczba $n$-elementowych multipodzbiorów zbioru $R$-elementowego.

Liczba $P$ wyraża się wielomianem względem $n$. Możemy w związku z tym w czasie wielomianowy przejrzeć wszystkie rozwiązania dopuszczalne i wybrać optymalne.

Uwaga

Niestety czas tego algorytmu jest wielomianem stopnia $R$. Jest to bardzo wysoki stopień i przez to algorytm ten nie może być traktowany jako praktyczne rozwiązanie problemu.

Lemat

Dla dowolnego $ϵ>0$ istnieje wielomianowy algorytm Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{1+\epsilon}} -aproksymacyjny dla problemu pakowania dla instancji, w których występują przedmioty o rozmiarach nie mniejszych niż $ϵ$.

Dowód

Algorytm dzielący na grupy.

1. Oblicz Parser nie mógł rozpoznać (nieznana funkcja „\ceil”): {\displaystyle \displaystyle K=\ceil{\frac{1}{\epsilon^2}}} .
2. Posortuj przedmioty względem rosnącego rozmiaru i podziel posortowany ciąg na $K$ grup tak, aby w każdej grupie było co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\floor”): {\displaystyle \displaystyle Q=\floor{n\epsilon^2}} przedmiotów.
3. Zamień rozmiar każdego z przedmiotów na rozmiar największego przedmiotu w tej samej grupie.
4. Użyj algorytmu z poprzedniego lematu działającego na przedmiotach o $K$ różnych rozmiarach nie mniejszych niż $ϵ$.

Niech $I$ będzie instancją podaną na wejściu algorytmu. Niech $I^{*}$ będzie instancją otrzymaną w trzecim kroku algorytmu, a $I_{*}$ instancją, którą otrzymalibyśmy zamieniając rozmiar każdego z przedmiotów na rozmiar najmniejszego w tej samej grupie.

Wynikiem działania algorytmu jest rozwiązanie optymalne dla instancji $I^{*}$. Musimy wykazać, że Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt(I^*) \leq \braq{1+\epsilon} \opt(I) } . Łatwo jest uzasadnić oszacowanie Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt(I_*) \leq \opt(I) } .

Możemy teraz zauważyć, że każde rozwiązanie instancjii $I_{*}$ wyznacza pewne rozwiązanie dla $I^{*}$. Ponieważ najmniejszy przedmiot z $i+1$ grupy przedmiotów jest większy lub równy największemu przedmiotowi z grupy $i$. Zatem rozwiązanie instancji $I_{*}$ pozwala upakować wszystkie przedmioty z instancji $I^{*}$ oprócz ostatniej grupy. Więc nawet jeżeli każdy z tych przedmiotów zostałby upakowany do osobnego pojemnika, otrzymujemy ograniczenie:

Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt(I^*) \leq \opt(I_*) + Q \leq \opt(I) + Q \leq \opt(I) + \floor{n\epsilon^2} \leq \braq{1+\epsilon} \opt(I) }

Ostatnia nierówność wynika z tego, że Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle n\epsilon \leq \opt(I) } . Pokazaliśmy zatem, że algorytm jest Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{1+\epsilon}} -aproksymacyjny.

Mając w ręku te dwa pomocnicze lematy możemy już pokazać algorytm ${{𝒜}}_{ϵ}$.

Algorytm ${{𝒜}}_{ϵ}$.

1. Stwórz instancję $I_{\ge ϵ}$ usuwając wszystkie przedmioty o rozmiarze mniejszym od $ϵ$ z $I$.
2. Oblicz instancję $I_{\ge ϵ}^{*}$ i znajdź dla niej optymalne upakowanie korzystając z algorytmu przeglądającego wszystkie rozwiązania dopuszczalne.
3. Dopakuj przedmioty o rozmiarze mniejszym od $ϵ$ za pomocą algorytmu First-Fit otrzymując rozwiązanie dla instancji wejściowej $I$.

Twierdzenie

Dla dowolnego $0<ϵ\le \frac{1}{2}$ algorytm ${{𝒜}}_{ϵ}$ znajduje upakowanie przedmiotów instancji $I$ w co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{1 + 2\epsilon} \opt(I) + 1} pojemnikach.

Dowód

Jeżeli w ostatnim kroku algorytmu nie zostały utworzone żadne nowe pojemniki, to rozwiązanie znalezione dla $I_{\ge ϵ}$ używa Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{1+\epsilon} \opt(I_{\geq\epsilon}) } pojemników, a więc spełnia warunki twierdzenia.

Jeżeli natomiast zostały utworzone nowe pojemniki, to zauważmy, że tylko w jednym ze wszystkich pojemników mogą znajdować się przedmioty o sumarycznym rozmiarze mniejszym niż $1-ϵ$. Zatem jeżeli oznaczymy przez $M$ liczbę wszystkich użytych pojemników, to sumarczyny rozmiar wszystkich przedmiotów (a więc i optimum) możemy ograniczyć z dołu przez Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{M-1}\braq{1-\epsilon}} . W związku z tym możemy napisać:

Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle M \leq \frac{ \opt(I) }{1-\epsilon} + 1 \leq \braq{1 + 2\epsilon} \opt(I) + 1 }

Druga nierówność wynika z prostego przekształcenia arytmetycznego przy $0<ϵ\le \frac{1}{2}$.

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

L-redukcje

Wprowadzimy teraz pojęcie redukcji zachowującej aproksymację. Pozwoli nam to na bardziej systematyczne niż do tej pory zbadanie klasy problemów, dla których możliwa jest aproksymacja. W dalszej części będziemy poszukiwać klasy problemów aproksymowalnych i problemów w tej klasie zupełnych względem podanej redukcji. Definicja interesującej nas redukcji jest podobna do tej jaką wprowadziliśmy pomiędzy problemami funkcyjnymi.

Definicja

Dla dwóch problemów optymalizacyjnych $A$ i $B$, parę funkcji $R:D_A\to D_B$ i $S:S_B\to S_A$ obliczalnych w pamięci logarytmicznej nazywamy L-redukcją, jeżeli istnieją dwie stałe dodatnie $\alpha$ i $\beta$ takie, że spełnione są następujące własności:

• Dla dowolnej instancji $x$ problemu $A$ zachodzi:

Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt_B( R(x) ) \leq \alpha \cdot \opt_A(x) }

• Dla dowolnego rozwiązania dopuszczalnego $s$ instancji $R(x)$ zachodzi:

Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{ \opt_A(x) - \obj_A(x, S(s) ) } \leq \beta \size{ \opt_B( R(x) ) - \obj_B( R(x) ,s) } }

Intuicyjnie, funkcja $R$ L-redukcji (redukcji liniowej) zamienia instancję problemu $A$ na instancję problemu $B$ nie zmieniając wartości rozwiązania optymalnego bardziej niż o stałą $\alpha$. Funkcja $S$ pozwala natomiast przeprowadzić dowolne z rozwiązań z powrotem na rozwiązanie instancji $A$ nie zmieniając odległości od optimum bardziej niż o stałą $\beta$.

Uwaga

Warto zauważyć, że definicja L-redukcji nie zależy od tego, czy problemy $A$ i $B$ są problami minimalizacyjnymi, czy maksymalizacyjnymi.

Przyjrzyjmy się teraz jeszcze raz redukcji problemu zbioru niezależnego do pokrycia wierzchołkowego. Jest ona oparta o fakt, że problemy te są do siebie dualne. Dopełnienie dowolnego zbioru niezależnego jest pokryciem wierzchołkowym i na odwrót.

Definicje odpowiednich funkcji są w związku z tym bardzo proste. $R$ to po prostu funkcja identycznościowa na grafach, a $S$ zwraca dopełnienie zbioru wierzchołków. Okazuje się, że nie jest to jednak L-redukcja, gdyż stosunku rozmiarów rozwiązań obu problemów nie da się w żaden sposób ograniczyć przez stałe.

Takie ograniczenie można uzyskać zawężając klasę grafów. Jeżeli ograniczymy maksymalny stopień wierzchołków występujących w grafie przez liczbę $k$, to otrzymamy problemy $k$-INDPENDENT SET i $k$-VERTEX COVER. Przypomnijmy, że z redukcji problemu $3$SAT wynika, że już problem $4$-INDEPENDENT SET jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełny.

Pokażemy, że funkcje $R$ i $S$ tworzą L-redukcję problemu $k$-INDEPENDENT SET do $k$-NODE COVER.

Zauważmy, że dla grafu Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle G=\braq{V,E}} ze stopniem wierzchołków ograniczonym przez $k$ rozmiar maksymalnego zbioru niezależnego to co najmniej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \frac{\size{V}}{k+1}} - dla każdego zbioru niezależnego o mniejszym rozmiarze, zbiór jego wszystkich sąsiadów jest co najwyżej $k$ razy większy i nie obejmuje w związku z tym całego grafu. Można zatem taki zbiór niezależny poszerzyć.

Tymczasem minimalne pokrycie wierzchołkowe ma w oczywisty sposób co najwyżej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{V}} elementów. W związku z tym możemy ustalić wartość parametru $\alpha$ na $k+1$.

Wystarczy teraz zauważyć, że odległość rozwiązania znalezionego od optymalnego nie zmienia się przy przejściu przez funkcję $S$. W związku z tym możemy ustalić wartość parametru $\beta$ na $1$.

Ta krótka analiza pozwala stwierdzić, że para Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{R,S}} jest L-redukcją problemu $k$-INDEPENDENT SET do $k$-NODE COVER.

Można też skonstruować odwrotną L-redukcję problemu $k$-NODE COVER do $k$-INDEPENDENT SET. Oczywiście należy użyć tych samych funkcji $R$ i $S$, ale żeby uzyskać liniową zależność rozmiaru maksymalnego zbioru niezależnego od minimlanego pokrycia wierzchołkowego trzeba się trochę postarać. Zauważmy, że dla antykliki rozmiar minimalnego pokrycia wierzchołkowego wynosi $0$, a maksymalny zbiór niezależny ma rozmiar równy ilości wierzchołków. Wynika stąd, że punkty izolowane mogą sprawiać problem dla L-redukcji.

W nowej redukcji funkcja $R$ będzie usuwać wierzchołki izolowane z grafu (które i tak nie należą do minimalnego pokrycia wierzchołkowego). Funkcja $S$ nadal będzie zamieniać zbiór wierzchołków na jego uzupełnienie (ale tylko w obrębie wierzchołków nie izolowanych). Rozmiar minimalnego pokrycia wierzchołkowego w grafie bez wierzchołków izolowanych wynosi co najmniej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \frac{\size{V}}{k}} - ponieważ jest co najmniej Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{V}} krawędzi, a każdy wierzchołek pokrywa co najwyżej $k$ z nich. To oszacowanie pozwala nam stwierdzić, że nowa redukcja jest L-redukcją z parametrami $k$ i $1$.

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}}

Wprowadzimy teraz formalną definicję klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} , która pozwoli nam bardziej metodycznie zbadać problemy optymalizacyjne. Dalsze badania nad tą klasą doprowadzą nas do bardzo ciekawych rezultatów dotyczących możliwości aproksymacji.

Zaczniemy od zdefiniowania klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} , która opisuje problemy maksymalizacyjne. Jej charakteryzacja jest analogiczna do charakteryzacji klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} podanej w twierdzeniu Fagina.

Definicja

Problem $A$ należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} , jeżeli można go wyrazić za pomocą formuły:

Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle \max_{S}\defset{\braq{x_1,x_2,\ldots,x_k} \in V^k}{ \phi(G_1,G_2,\ldots,G_m,S,x_1,x_2,\ldots,x_k) } }

Wejściem dla problemu $A$ jest ciąg relacji (być może wieloargumentowych) $G_i,i=1,2,\dots ,m$ nad skończonym uniwersum $V$. Poszukiwana jest natomiast relacja $S$, która maksymalizowałaby liczbę naborów zmiennych $x_i$ takich że formuła pierwszego rzędu bez kwantyfikatorów $\varphi$ jest spełniona.

Definicja

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} jest domknięciem Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} ze względu na L-redukcje.

Zobaczmy teraz przykład problemu, który należy do Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} . Wybierzemy problem $k$-INDEPENDENT SET. Zwykła reprezentacja grafu poprzez relację binarną nie pozwala wygodnie przedstawić ograniczenia stopnia wierzchołka i raczej nie prowadzi do reprezentacji poprzez odpowiednią formułę. Dlatego użyjemy niestandardowej reprezentacji grafu poprzez $k+1$-argumentową relację $H$. Każdemu wierzchołkowi $G$ odpowiada jedna krotka relacji $H$ - Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{x,y_1,y_2,\ldots,y_k}} , która koduje sąsiedztwo wierzchołka $x$. Wierzchołki $y_1,y_2,\dots ,y_k$ to sąsiedzi $x$. Jeżeli $x$ nie ma $k$ sąsiadów, to na brakujących pozycjach występuje $x$. Problem $k$-zbioru niezależnego koduje się wtedy w następujący sposób:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned \max_{S\subseteq V}\{\braq{x,y_1,y_2,\ldots,y_k} \in V^k : \braq{x,y_1,y_2,\ldots,y_k} \in H \wedge x \in S \wedge \\ \wedge \left[x = y_1 \vee y_1 \notin S\right] \wedge \left[ x = y_2 \vee y_2 \notin S\right] \wedge \ldots \wedge \left[ x = y_k \vee y_k \notin S\right]\} \endaligned}

Wybór relacji $S$ koduje pewien podzbiór wierzchołków. Formuła kodująca problem jest spełniona dla krotek odpowiadających tym wierzchołkom $x$, które należą do wybranego zbioru, a żaden z sąsiadów nie należy. Odpowiada to więc zbiorowi niezależnemu.

Pokazaliśmy zatem, że problem $k$-INDEPENDENT SET należy do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} . Natychmiastowym wnioskiem jest, że problem $k$-NODE COVER jest problemem z Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} . Znamy przecież jego L-redukcję do $k$-INDEPENDENT SET.

Ćwiczenie

{{{3}}}

Problemy MAXSAT i MAX FUNCTION SAT

Problem maksymalnej spełnialności MAXSAT i jego zawężenia pełnią podobną rolę dla klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} jak problem SAT dla Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} . W tej części przyjrzymy się dokładniej temu problemow i jego różnym wersjom. Podamy również algorytmy aproksymacyjne i udowodnimy zupełność zawężeń tego problemu dla klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} .

Przypomnijmy, że na wejściu problemu MAXSAT dostajemy formułę logiczną w koniunkcyjnej postaci normalnej z $n$ zmiennymi. Poszukujemy takiego wartościowania tych zmiennych, które zmaksymalizowałoby liczbę spełnionych klauzul. Dla wygody dodajemy warunek, aby każda z klauzul była inna.

$\frac{1}{2}$-aproksymację problemu MAXSAT można osiągnąć bardzo prostą metodą:

Algorytm wybierający wartościowanie $x$ lub $\bar{x}$.

1. Wybierz dowolne wartościowanie $x$ dla $n$ zmiennych występujących w formule.
2. Skonstruuj wartościowanie $\bar{x}$, które przyporządkowuje zmiennym wartościowanie odwrotne do $x$.
3. Jako wynik podaj to z wartościowań $x$, $\bar{x}$, przy którym więcej klauzul jest spełnionych.

Twierdzenie

Podany algorytm jest algorytmem $\frac{1}{2}$-aproksymacyjnym.

Dowód

Zauważmy, że jeżeli któraś z alternatyw jest niespełniona przy wartościowaniu $x$, to musi być spełniona przy wartościowaniu $\bar{x}$. Jeżeli alternatywa jest niespełniona przy jakimś wartościowaniu, to znaczy, że każda ze zmiennych występujących w klauzuli jest wartościowana odwrotnie niż jej wystąpienie. Zatem przy wartościowaniu odwrotnym każdy z literałów występujących w alternatywie jest wartościowany pozytywnie i alternatywa musi być spełniona.

Jeżeli zatem oznaczymy przez $m$ - liczbę alternatyw w formule, przez $c$ - liczbę alternatyw spełnionych przy wartościowaniu $x$, a przez $\bar{c}$ - liczbę alternatyw spełnionych przy wartościowaniu $\bar{x}$, to zachodzą następującee nierówności:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned c &\geq m - \overline{c} \\ \overline{c} &\geq m - c \\ c + \overline{c} &\geq 2m - c - \overline{c} \\ c + \overline{c} &\geq m \endaligned}

Ponieważ algorytm wybiera to z wartościowań $x$ lub $\bar{x}$, przy którym więcej alternatyw jest spełnionych, to liczba spełnionych alternatyw jest nie mniejsza niż $\frac{1}{2}m$. Nawet jeżeli rozwiązanie optymalne zapewnia spełnienie wszystkich $m$ alternatyw, to algorytm jest $\frac{1}{2}$-aproksymacyjny.

Pokażemy teraz pewną wariację na temat problemu MAXSAT.

Problem

Problem maksymalnej spełnialności funkcyjnej MAX FUNCTION SAT

Danych jest $n$ zmiennych logicznych $x_1,x_2,\dots ,x_n$ oraz $m$ funkcji logicznych $f_1,f_2,\dots ,f_m$. Należy znaleźć wartościowanie zmiennych $x_1,x_2,\dots ,x_n$ przy którym największa liczba funkcji daje wynik pozytywny.

Ciekawym i istotnym dla dalszych rozważań zawężeniem problemów MAXSAT i MAX FUNCTION SAT jest ograniczenie liczby różnych zmiennych występujących w pojedynczej klauzuli lub funkcji logicznej. Jeżeli ta liczba jest ograniczonaa przez $k$, to mamy do czynienia z problemem MAX$k$SAT i MAX$k$FSAT.

Przypomnijmy, że pokazaliśmy, że już problem MAX$2$SAT jest Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{NP}} -zupełny (mimo że problem $2$SAT nie jest). Teraz okaże się dlaczego te problemy są dla nas tak interesujące:

Twierdzenie

Problemy MAX$k$SAT należą do klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} .

Dowód

Pokażemy, że problem MAX$2$SAT należy do Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} . Konstrukcja reprezentacji formuły i kodowania problemu dla większych $k$ jest analogiczna.

Zatem ustalamy, że uniwersum $V$ to zbiór zmiennych występujących w formule, a trzy relacje binarne $G_0,G_1,G_2$ kodują formułę. Para Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{x_1,x_2}} w relacji $G_i$ koduje wystąpienie klauzuli zawierającej literały $x_1$ i $x_2$ z których $i$ występuje pozytywnie. Żeby zapewnić reprezentację każdej alternatywy przez dokładnie jedną krotkę którejś z relacji wprowadzamy taką odpowiedniość pomiędzy relacjami i klauzulami:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned G_0(x_i,x_j) & \Longleftrightarrow & \braq{\neg x_i \vee \neg x_j}; i < j \\ G_1(x_i,x_j) & \Longleftrightarrow & \braq{x_i \vee \neg x_j} \\ G_2(x_i,x_j) & \Longleftrightarrow & \braq{x_i \vee x_j}; i < j \endaligned}

Możemy teraz użyć następującej formuły reprezentującej problem MAX$2$SAT:

Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle \max_{S\subseteq V}\defset{\braq{x,y}}{\left[ G_0(x,y) \wedge \braq{\neg S(x) \vee \neg S(y) }\right] \vee \left[ G_1(x,y) \wedge \braq{ S(x) \vee \neg S(y) }\right] \vee \left[ G_2(x,y) \wedge \braq{ S(x) \vee S(y) }\right]} }

Wybór relacji $S$ odpowiada ustaleniu wartościowania, a konstrukcja formuły zapewnia, że liczba krotek Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle \braq{x,y}} spełniających formułę odpowiada liczbie alternatyw spełnionych przy danym wartościowaniu.

Zbudowanie algorytmu aproksymacyjnego dla problemu MAX$k$FSAT nie jest już tak proste, jak dla problemu MAXSAT. Załóżmy, że mamy $n$ zmiennych $x_1,x_2,\dots ,x_n$ i $m$ funkcji logicznych $f_1,f_2,\dots ,f_m$, z których każda zależy od co najwyżej $k$ zmiennych. Żeby dobrze zobrazować działanie algorytmu wyobraźmy sobie pełne drzewo binarne o $2^n$ liściach. Każdy węzeł wewnętrzny reprezentuje pewne częściowe wartościowanie zmiennych.

{drzewo wartościowań - ZO-8.2}

Dla każdego węzła drzewa $t$ i funkcji $f_i$ określamy funkcję:

$p(t,f_i)=\frac{\text{liczba wartościowań rozszerzających }t\text{ przy których }{f}_i\text{ daje wynik pozytywny}}{\text{liczba wszystkich wartościowań rozszerzających }t}$

Łatwo zauważyć, że jeżeli węzły $t_0$ i $t_1$ są dziećmi $t$ w drzewie wartościowań, to zachodzi:

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle p(t,f_i) = \frac{1}{2}\braq{ p(t_0,f_i) + p(t_1,f_i) } }

Rozważmy teraz funkcję $P(t)=\sum _{i=1}^{m}p(t,f_i)$. Oczywistym wnioskiem z poprzedniej równości jest:

Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle P(t) = \frac{1}{2}\braq{ P(t_0) + P(t_1) } }

Zauważmy jeszcze, że obliczenia wartości $P(t)$ dla konkretnego $t$ można dokonać w czasie wielomianowym. Ponieważ każda z funkcji $f_i$ zależy tylko od $k$ zmiennych, więc można dokonać wyczerpującego przeglądu wszystkich $2^k$ wartościowań tych zmiennych zliczając te dla których $f_i$ daje wynik pozytywny i są rozszerzeniami wartościowania $t$. Można zatem w czasie wielomianowym zsumować wartości $p(t,f_i)$ dla wszystkich $m$ funkcji $f_i$.

Możemy już teraz przedstawić algorytm:

Algorytm schodzący po drzewie wartościowań

1. Ustaw zmienną $t$ na korzeń $r$ drzewa wartościowań.
2. Dopóki $t$ nie będzie liściem drzewa wartościowań:

Obliczaj wartość $P(t_0)$ i $P(t_1)$ dla dzieci węzła $t$ i ustaw $t$ na to z dzieci, dla którego wartość $P(t_i)$ jest większa.

Podaj wartościowanie opisywane przez węzeł $t$ jako wynik.

Twierdzenie

Algorytm schodzący po drzewie wartościowań jest algorytmem $\frac{1}{2^k}$-aproksymacyjnym dla problemu MAX$k$FSAT.

Dowód

Liczba funkcji dających wynik pozytywny przy wartościowaniu $t$ znalezionym przez algorytm jest równa dokładnie $P(t)$. Ponieważ węzeł $t$ określa wartość każdej ze zmiennych, to $p(t,f_i)$ jest równe $1$ dla funkcji dających wynik pozytywny, a $0$ dla tych dających wynik negatywny.

Zauważmy, że $P(t)\ge P(r)$. Jest tak dlatego, że przy każdym zejściu w dół drzewa od węzła $s$ jest spełnione Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle P(s) = \frac{1}{2}\braq{ P(s_0) + P(s_1) }} , więc któraś z wartości $P(s_0)$, lub $P(s_1)$ jest większa lub równa $P(s)$, a algorytm wybiera zejście w kierunku większej z nich. W związku z tym wartość funkcji $P$ dla aktualnie przeglądanego węzła nigdy nie maleje.

Zatem liczba funkcji z wynikiem pozytywnym w rozwiązaniu znalezionym przez algorytm jest nie mniejsza niż Parser nie mógł rozpoznać (nieznana funkcja „\ceil”): {\displaystyle \displaystyle \ceil{ P(r) }} . Ponieważ dla każdej funkcji, która może w ogóle dać wynik pozytywny przy jakimkolwiek wartościowaniu zachodzi $p(r,f_i)\ge \frac{1}{2^k}$, to liczba funkcji, które dają wynik pozytywny w rozwiązaniu optymalnym jest ograniczona z góry przez $\frac{P(r)}{\frac{1}{2^k}}$. To dowodzi że algorytm jest algorytmem $\frac{1}{2^k}$-aproksymacyjnym.

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

Problemy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełne

Pokażemy teraz, że problem MAX$3$SAT jest problemem zupełnym w sensie L-redukcji w klasie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} . Jest to bardzo istotny fakt, bo oznacza, że pozytywne wyniki aproksymacjii tego elementarnego problemu przekładają się poprzez L-redukcje na wszystkie problemy z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} . Jest też to fakt interesujący ze względu na to, że wcale nie jest oczywiste, że problemy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} -zupełne muszą w ogóle istnieć.

Twierdzenie

MAX$3$SAT jest problemem zupełnym w sensie L-redukcji w klasie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} .

Dowód

Przypomnijmy, że klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}} jest definiowana jako klasa problemów L-redukowalnych do problemów z Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} . Zatem wystarczy, że pokażemy, że każdy problem z Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} jest L-redukowalny do problemu MAX$3$SAT i skorzystamy z tego, że złożenie L-redukcji jest L-redukcją.

Rozważmy zatem problem $A$ z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \displaystyle \cc{MAXSNP}_0} definiowany formułą:

Parser nie mógł rozpoznać (nieznana funkcja „\defset”): {\displaystyle \displaystyle \max_S\defset{\braq{x_1,x_2,\ldots,x_k}}{\phi} }

Rozważymy teraz konkretną instancję problemu $A$ z ustalonym uniwersum $V$ i relacjami $G_1,G_2,\dots ,G_m$. Dla każdej krotki Parser nie mógł rozpoznać (nieznana funkcja „\braq”): {\displaystyle \displaystyle v = \braq{v_1,v_2,\ldots,v_k} \in V^k} definiujemy formułę ${\varphi }_v$, która powstaje z $\varphi$ przez podstawienie wartości $v_1,v_2,\dots ,v_k$ za zmienne $x_1,x_2,\dots ,x_k$. Każdą w formuł ${\varphi }_v$ możemy uprościć zamieniając każde wystąpienie relacji $G$ i symbolu $=$ wartościami prawdy i fałszu, które w konkretnej instancji są ustalone. W wyniku otrzymujemy formułę ${\varphi }_v$, w której występują tylko symbole logiczne i relacja $S$.

Możemy teraz spojrzeć na rozwiązanie tej instancjii problemu $A$ jak na ustalenie wartościowania formuł $S(v_{i_1},v_{i_2},\dots ,v_{i_r})$ tak aby zmaksymalizować liczbę spełnionych formuł ${\varphi }_v$. Jeżeli któraś z formuł ${\varphi }_v$ jest niespełnialna dla żadnego wartościowania, to już na tym etapie usuwamy ją z opisu problemu.

Właśnie opisaliśmy redukcję problemu $A$ do problemu MAX$l$FSAT, gdzie jest Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{V}^r} zmiennych odpowiadających $S(v_{i_1},v_{i_2},\dots ,v_{i_r})$ i Parser nie mógł rozpoznać (nieznana funkcja „\size”): {\displaystyle \displaystyle \size{V}^r} funkcji logicznych odpowiadających formułom ${\varphi }_v$. Stała $l$ zależy tylko od postaci formuły $\varphi$ i należy ją ustalić równą liczbie wystąpień symbolu relacyjnego $S$ w formule $\varphi$. Możemy teraz użyć redukcji MAX$l$FSAT do MAX$3$SAT.

Musimy teraz pokazać, że otrzymana w ten sposób redukcja jest L-redukcją. Na podstawie instancji $x$ problemu $A$ możemy zbudować $R(x)$ instancję problemu MAX$3$SAT. Rozwiązanie $S(s)$ możemy łatwo obliczyć odczytując relację $S$ z wartości zmiennych występujących w rozwiązaniu problemu $R(x)$.

Musimy teraz skorzystać z pewnych własności problemu MAX$l$FSAT i jego redukcji do MAX$3$SAT.

Po pierwsze - każda formuła ${\varphi }_v$ jest reprezentowana przez co najwyżej $c$ klauzul, gdzie $c$ zależy tylko od liczby bramek potrzebnych do wyrażenia formuły $\varphi$.

Po drugie - istnieje stała $d$ taka, że dla $m$ funkcji w problemie MAX$l$SAT istnieje wartościowanie, przy którym przynajmniej $dm$ spośród funkcji ma wartość pozytywną. Skorzystamy z tego, że odrzuciliśmy funkcje, które stale przyjmują wartość negatywną. Stałą $d$ równą $\frac{1}{2^l}$ otrzymujemy z dowodu, że algorytm schodzący po drzewie wartościowań jest algorytmem $\frac{1}{2^l}$-aproksymacyjnym.

Po trzecie - zastosowana redukcja MAX$l$FSAT do MAX$3$SAT gwarantuje, że w rozwiązaniu optymalnym problemu $R(x)$ wszystkie klauzule poza tymi przechowującymi wyniki funkcji są spełnione.

Te trzy fakty sprawiają, że opisana redukcja jest L-redukcją z parametrami $\alpha =\frac{c}{d}$ (Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt(x) \geq dm} , Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt( R(x) ) \leq cm} ) i $\beta =1$ (w rozwiązaniu optymalnym Parser nie mógł rozpoznać (nieznana funkcja „\opt”): {\displaystyle \displaystyle \opt} problemu $R(x)$ liczba spełnionych alternatyw zmniejszona o liczbę alternatyw innych niż przechowujące wyniki funkcji wyznacza dokładnie liczbę krotek $V^k$, dla których relacja $S$ zachodzi).

Ćwiczenie

{{{3}}}