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

From Studia Informatyczne

Spis treści

Wprowadzenie

W 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ę \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 2.1

Mówimy, że algorytm \displaystyle \mathcal{A} jest {schematem aproksymacji} dla problemu \displaystyle \cc{NP}-optymalizacyjnego \displaystyle \Pi, jeżeli dla wejścia \displaystyle (\braq{I,\epsilon}), gdzie \displaystyle I jest instancją problemu \displaystyle \Pi, a \displaystyle \epsilon > 0 opisuje dopuszczalny błąd, znajduje rozwiązanie takie, że:

  • \displaystyle  \textnormal{obj}_\Pi(I,{ \mathcal{A}(I,\epsilon) })  \leq (\braq{1 + \epsilon})   \textnormal{opt}\displaystyle  _\Pi(I) dla problemu minimalizacji.
  • \displaystyle  \textnormal{obj}_\Pi(I,{ \mathcal{A}(I,\epsilon) })  \geq (\braq{1 - \epsilon}) \textnormal{opt}\displaystyle  _\Pi(I) dla problemu maksymalizacji.

Definicja 2.2

Jeśli dla dowolnego \displaystyle \epsilon > 0 czas działania \displaystyle \mathcal{A} na wejściu \displaystyle (\braq{I,\epsilon}) jest wielomianowy względem \displaystyle |\size{I}|, to \displaystyle \mathcal{A} 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 \displaystyle \epsilon. Nie jest to sytuacja komfortowa. Możemy w związku z tym wzmocnić wymagania postawione dla algorytmu.

Definicja 2.3

Jeżeli czas działania algorytmu \displaystyle \mathcal{A} jest wielomianowy względem \displaystyle |\size{I}| oraz wartości \displaystyle \frac{1}{\epsilon}, to \displaystyle \mathcal{A} jest {w pełni wielomianowym schematem aproksymacji}. Omawiając takie algorytmy, będziemy używać notacji FPTAS (fully polynomial time approximation scheme).

Ćwiczenie 2.4

FPTAS dla problemów silnie \displaystyle \cc{NP}-zupełnych.

Wykaż, że o ile \displaystyle \cc{P} \neq \cc{NP} i \displaystyle \Pi jest silnie \displaystyle \cc{NP}-zupełnym problemem optymalizacyjnym takim, że funkcja celu \displaystyle \textnormal{obj}_\Pi przyjmuje wartości całkowite i ograniczone wielomianowo od rozmiaru instancji wejściowej oraz jej największej liczby, to nie istnieje algorytm FPTAS dla \displaystyle \Pi.

Wskazówka

Wykorzystaj ograniczenie na wartości funkcji celu do zdefiniowania odpowiedniego progu dopuszczalnego błędu w algorytmie FPTAS. Otrzymasz algorytm pseudowielomianowy dla silnie \displaystyle \cc{NP}-zupełnej decyzyjnej wersji problemu \displaystyle \Pi.

Rozwiązanie

Niech \displaystyle \Pi będzie problemem maksymalizacji z funkcją celu \displaystyle \textnormal{obj}_\Pi (dla problemu minimalizacji dowód przebiega analogicznie). Załóżmy, że jej wartości są całkowite dodatnie oraz dla każdej instancji \displaystyle I, \displaystyle \textnormal{obj}_\Pi(I) < p(|I|,NUM(I)), gdzie \displaystyle p jest pewnym wielomianem dwóch zmiennych, a \displaystyle NUM(I) jest skojarzoną z problemem funkcją określającą wartość największej liczby występującej w instancji. Załóżmy, że \displaystyle A jest FPTAS dla \displaystyle \Pi. Skonstruujemy algorytm pseudowielomianowy dla \displaystyle \Pi.

Na wejściu dana jest instancja \displaystyle I. Algorytm składa sie z dwóch

kroków:

1. oblicz \displaystyle \delta = 1/p(|I|,NUM(I)),

2. zastosuj \displaystyle A dla instancji \displaystyle I i dokładności \displaystyle \delta obliczone

rozwiązanie dopuszczalne \displaystyle S wypisz na wyjście.

Ponieważ \displaystyle \Pi jest maksymalizacyjny, więc \displaystyle \textnormal{obj}_\Pi(I,S)\geq (1-\delta). Zatem \displaystyle \textnormal{opt}(I)-\textnormal{obj}_\Pi(I,S) \leq \delta \, \textnormal{opt}(I) < 1.

Z tego, że wartości funkcji celu są całkowitoliczbowe, wynika

\displaystyle \textnormal{obj}_\Pi(I,S)=\textnormal{opt}(I), a zatem nasz algorytm znajduje rozwiązania optymalne. Zgodnie z definicją FPTAS, algorytm działa w czasie wielomianowym od \displaystyle |I| oraz \displaystyle 1/\delta, jest to więc algorytm pseudowielomianowy dla \displaystyle \Pi.

Z analizowanych w poprzednim wykładzie własności silnej

NP-zupełności wynika, że musi to być algorytm wielomianowy dla \displaystyle \Pi, co oczywiście jest sprzeczne z założeniem \displaystyle \cc{P} \neq \cc{NP}.

Schemat aproksymacji dla problemu KNAPSACK

Pokazaliśmy, że nie warto szukać algorytmów FPTAS dla problemów silnie \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 \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 pseudowielomianowy rozwiązujący problem KNAPSACK. Poznaliśmy już jeden taki alorytm, ale tamten nie nadaje się do konstrukcji schematu aproksymacji.

Algorytm 3.1 [Algorytm pseudowielomianowy dla problemu plecakowego]


1. Oblicz \displaystyle V = \max_{i=1,2,\ldots,n}  v(a_i).

2. Oblicz \displaystyle W_{i,u} określone dla \displaystyle 0 \leq i \leq n i \displaystyle 0 \leq u \leq nV jako "minimalny sumaryczny rozmiar podzbioru przedmiotów \displaystyle S \subseteq{a_1,a_2,\ldots,a_i} taki, że sumaryczna wartość tych przedmiotów wynosi dokładnie \displaystyle u". Obliczenia można dokonać metodą dynamiczną, korzystając z następujących własności rekurencyjnych: \displaystyle \aligned W_{0,u} &= \infty\textnormal{,} \\ W_{i+1,u} &=  \min(W_{i,u},W_{i,u- v(a_{i+1}) }+ w(a_{i+1}) )\textnormal{.} \endaligned

3. Odczytaj rozwiązanie z wartości \displaystyle W.

Algorytm ten można zakodować tak, aby znajdował optymalne rozwiązanie w czasie \displaystyle \mathcal{O}({n^2V}). Szczegóły implementacji pozostawiamy jako ćwiczenie.

Zauważmy, że gdyby wartości przedmiotów były ograniczone przez wielomianową funkcję \displaystyle 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 \displaystyle n i \displaystyle \frac{1}{\epsilon}. Oto algorytm:

Algorytm 3.2 [Algorytm zaokrągleniowy]


1. Oblicz \displaystyle K = \frac{\epsilon V}{n}.

2. Dla każdego przedmiotu oblicz \displaystyle  v'(a_i)  = [\floor{\frac{ v(a_i) }{K}}].

3. Używając algorytmu pseudowielomianowego, rozwiąż problem z wartościami \displaystyle v'.

Twierdzenie 3.3

Algorytm zaokrągleniowy jest FPTAS dla problemu plecakowego.

Dowód

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

\displaystyle \sum_{i \in S}  v(a_i)  \geq (\braq{1 - \epsilon})  \textnormal{opt}\textnormal{.}

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

\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\textnormal{.}

Korzystamy po kolei z własności zaokrąglenia, optymalności rozwiązania \displaystyle S przy wartościach wydzielonych przez \displaystyle K, własności zaokrąglenia i tego, że \displaystyle |\size{S}| \leq n.

Udowodniliśmy, że wartość rozwiązania znajdowanego przez algorytm jest nie mniejsze niż \textnormal{opt} \displaystyle   - nK =  \textnormal{opt} \displaystyle   - \epsilon V \geq (\braq{1-\epsilon}) \textnormal{opt}. Jest to zatem schemat aproksymacyjny. Musimy jeszcze oszacować czas działania algorytmu. Wynosi on \displaystyle \mathcal{O}({n^2[\floor{\frac{V}{K}}]}) = \mathcal{O}({n^2[\floor{\frac{n}{\epsilon}}]}), a więc jest wielomianowy zarówno względem \displaystyle n, jak i \displaystyle \frac{1}{\epsilon}.

image:End_of_proof.gif

Ćwiczenie 3.4

Algorytm pseudowielomianowy.

Doprecyzuj implementację algorytmu pseudowielomianowego dla problemu plecakowego. Jak odzyskać wybór przedmiotów z tablicy \displaystyle W_{i,u}?

Wskazówka

Użyj standardowej konstrukcji algorytmu dynamicznego w oparciu o podane własności rekurencyjne.

Rozwiązanie

Następujący program wypełni tablicę \displaystyle W_{i,u}:

for \displaystyle u=0,1,\ldots,V do
  \displaystyle W_{0,u} = \infty
end for
for \displaystyle i=1,2,\ldots,n do
  for \displaystyle u=0,1,\ldots,nV do
    \displaystyle W_{i,u} = W_{i-1,u}
    if \displaystyle u- v(a_i)  \geq 0 and \displaystyle W_{i-1,u- v(a_i) }+ w(a_i)  < W_{i,u} then
      \displaystyle W_{i,u} = W_{i-1,u- v(a_i) }+ w(a_{i})
    end if
  end for
end for

A ten pozowoli odszukać rozwiązanie optymalne:

\displaystyle S=\emptyset
\displaystyle o=0
for \displaystyle u=0,1,\ldots,nV do
  if \displaystyle W_{n,u} \leq B
    \displaystyle o=u
  end if
end for
\displaystyle i=n
while \displaystyle o > 0 do
  if \displaystyle W_{i,o} = W_{i-1,o} then
    \displaystyle i = i-1 
  else
    \displaystyle S = S \cup \{i\}
    \displaystyle o = o -  v(a_i)
    \displaystyle i = i-1
  end if
end while
return \displaystyle S

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 \displaystyle \cc{NP}-zupełny i o ile \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 \displaystyle \frac{3}{2}. Dowód opierał się o fakt, że o ile \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ż \displaystyle \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 \displaystyle \mathcal{A}_\epsilon dla \displaystyle 0 < \epsilon \leq \frac{1}{2} działających w czasie wielomianowym od liczby przedmiotów i znajdujących rozwiązanie używające co najwyżej \displaystyle (\braq{1 + 2\epsilon}) \textnormal{opt} \displaystyle   + 1 pojemników.

Zanim będziemy mogli przedstawić algorytmy \displaystyle \mathcal{A}_\epsilon musimy pokazać dwa pomocnicze lematy, które pokazują rozwiązania dla pewnych uproszczonych instancji problemu.

Lemat 4.1

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

Dowód

Liczba przedmiotów w jednym pojemniku jest ograniczona przez \displaystyle M=[\floor{\frac{1}{\epsilon}}]. Suma rozmiarów większej liczby przedmiotów musi przekraczać \displaystyle 1, gdyż każdy z nich ma rozmiar nie mniejszy niż \displaystyle \epsilon.

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

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

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

image:End_of_proof.gif
Uwaga 4.2

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

Lemat 4.3

Dla dowolnego \displaystyle \epsilon > 0 istnieje wielomianowy algorytm \displaystyle (\braq{1+\epsilon})-aproksymacyjny dla problemu pakowania dla instancji, w których występują przedmioty o rozmiarach nie mniejszych niż \displaystyle \epsilon.

Dowód

{{{3}}} image:End_of_proof.gif

Mając w ręku te dwa pomocnicze lematy, możemy już pokazać algorytm \displaystyle \mathcal{A}_\epsilon.

Algorytm 4.5 [Algorytm \displaystyle \mathcal{A}_\epsilon]


1. Stwórz instancję \displaystyle I_{\geq\epsilon}, usuwając wszystkie przedmioty o rozmiarze mniejszym od \displaystyle \epsilon z \displaystyle I.

2. Oblicz instancję \displaystyle I_{\geq\epsilon}^* i znajdź dla niej optymalne upakowanie, korzystając z algorytmu przeglądającego wszystkie rozwiązania dopuszczalne.

3. Dopakuj przedmioty o rozmiarze mniejszym od \displaystyle \epsilon za pomocą algorytmu First-Fit, otrzymując rozwiązanie dla instancji wejściowej \displaystyle I.

Twierdzenie 4.6

Dla dowolnego \displaystyle 0 < \epsilon \leq \frac{1}{2} algorytm \displaystyle \mathcal{A}_\epsilon znajduje upakowanie przedmiotów instancji \displaystyle I w co najwyżej \displaystyle (\braq{1 + 2\epsilon}) \textnormal{opt} \displaystyle  (I)  + 1 pojemnikach.

Dowód

Jeżeli w ostatnim kroku algorytmu nie zostały utworzone żadne nowe pojemniki, to rozwiązanie znalezione dla \displaystyle I_{\geq\epsilon} używa \displaystyle (\braq{1+\epsilon}) \textnormal{opt} \displaystyle  (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ż \displaystyle 1 - \epsilon. Zatem jeżeli oznaczymy przez \displaystyle 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 \displaystyle (\braq{M-1})(\braq{1-\epsilon}). W związku z tym możemy napisać:

\displaystyle M \leq \frac{ \textnormal{opt} \displaystyle  (I) }{1-\epsilon} + 1 \leq (\braq{1 + 2\epsilon}) \textnormal{opt} \displaystyle  (I)  + 1\textnormal{.}

Druga nierówność wynika z prostego przekształcenia arytmetycznego przy \displaystyle 0 < \epsilon \leq \frac{1}{2}.

image:End_of_proof.gif

Ćwiczenie 4.7

Aproksymacja dla problemu PARTITION.

Optymalizacyjna wersja problemu PARTITION powstaje, kiedy chcemy wybrać podzbiór \displaystyle A' \subseteq A taki, że minimalizuje wartość \displaystyle |\size{\sum_{a \in A'}| s(a)  - \sum_{a \in A \setminus A'}  s(a) }|.

Uzasadnij, że dla tego problemu nie ma algorytmu PTAS.

Inna wersja optymalizacyjna problemu PARTITION powstaje, kiedy mierzymy odległość od równomiernego podziału przez iloraz zamiast przez różnicę. Chcemy wtedy wybrać podzbiór \displaystyle A' \subseteq A taki, że iloraz:

\displaystyle \frac{\sum_{a \in A'}  s(a) }{\sum_{a \in A \setminus A'}  s(a) } \geq 1\textnormal{,}

jednocześnie minimalizując wartość tego ilorazu.

Pokaż algorytm FPTAS dla tej wersji problemu PARTITION.

Wskazówka

Zauważ, że optimum dla pierwszego problemu wynosi \displaystyle 0 wtedy i tylko wtedy, gdy elementy wejściowe są pozytywnym przykładem dla zwykłego problemu PARTITION.

Konstrukcję FPTAS dla drugiego problemu rozpocznij od przypomnienia sobie algorytmu pseudowielomianowego.

Rozwiązanie

Pokażemy, że dla pierwszego problemu nie istnieje żaden algorytm \displaystyle a-aproksymacyjny. To w oczywisty sposób pociąga za sobą brak algorytmu PTAS. Ponieważ optimum dla pierwszego problemu wynosi \displaystyle 0 tylko dla takiego zbioru \displaystyle A, który da się podzielić na dwie równe części, więc dowolny algorytm \displaystyle a-aproksymacyjny musiałby znajdować rozwiązanie nie większe niż \displaystyle a\cdot 0 = 0 i tym samym rozstrzygać problem PARTITION.

Żeby skonstruować FPTAS dla drugiego problemu, załóżmy, że \displaystyle A=\{a_1,a_2,\ldots,a_n\} i przypomnijmy, że znamy algorytm pseudowielomianowy dla tego problemu.

Algorytm FPTAS dla tego problemu powstaje poprzez zaokrąglenie liczb podanych na wejściu i wykonanie pseudowielomianowego algorytmu dokładnego.

Przyjmując \displaystyle T=\sum_{i=1}^n  s(a_i) i \displaystyle K=\frac{\epsilon T}{4n} i znajdując rozwiązanie dokładne przy \displaystyle  s'(a)  = \frac{ s(a) }{K}, możemy przeprowadzić analizę podobną do tej wykorzystanej w problemie KNAPSACK. Są jednak subtelne różnice.

Może się zdarzyć, że podzbiór \displaystyle A' znaleziony przy wagach \displaystyle s' nie jest rozwiązaniem dopuszczalnym przy wagach \displaystyle s, gdyż \displaystyle \frac{\sum_{a \in A'}  s'(a) }{\sum_{a \in A\setminus A'}  s'(a) } \geq 1 nie pociąga za sobą takiej samej nierówności przy wagach \displaystyle s. Z problemem tym możemy sobie na szczęście łatwo poradzić, zamieniając znaleziony zbiór \displaystyle A' na \displaystyle A\setminus A'. Dalszą analizę przeprowadzimy tylko w przypadku, kiedy nie jest potrzebna taka zamiana, gdyż drugi przypadek jest analogiczny.

Możemy zatem zapisać następujący ciąg nierówności, gdzie \displaystyle O jest rozwiązaniem optymalnym:

\displaystyle \frac{T}{2} \leq \sum_{a \in A'}  s(a)  \leq \sum_{a \in A'} [\floor{\frac{ s(a) +K}{K}}]K \leq \sum_{a \in O} [\floor{\frac{ s(a) }{K}}]K + Kn \leq \textnormal{opt} \displaystyle   + 2Kn \leq \textnormal{opt} \displaystyle   + \epsilon\frac{T}{2} \leq (\braq{1+\epsilon}) \textnormal{opt}\textnormal{.}

Przy przekształceniach korzystamy z własności zaokrągleń, a ostatnia nierówność wynika z tego, że \textnormal{opt} \displaystyle   \geq \frac{T}{2}.

Ćwiczenie 4.8

Problem BIN COVERING.

Rozważ problem dualny do BIN PACKING:

Problem

Pokrywanie BIN COVERING.

Mając dany zbiór \displaystyle n przedmiotów o wagach wymiernych \displaystyle w_1,w_2,\ldots,w_n\in(0,1], należy znaleźć przyporządkowanie ich do jak największej liczby pojemników. Suma wag przedmiotów w jednym pojemniku musi przekraczać \displaystyle 1, a część przedmiotów może być w ogóle niewykorzystana.

Można się domyślać, że problem ten ma charakterystykę podobną do BIN PACKING.

Pokaż, że o ile \displaystyle \cc{P} \neq \cc{NP}, to nie ma dla niego algorytmu \displaystyle a-aproksymacyjnego dla \displaystyle a>\frac{1}{2}. Skonstruuj asymptotyczny PTAS przy dodatkowym założeniu, że rozmiary wszystkich przedmiotów są większe niż pewna stała \displaystyle c>0 (istnieje również asymptotyczny PTAS bez tego dodatkowego założenia, ale jego analiza jest znacznie trudniejsza).

Wskazówka

Wykorzystaj te same techniki co w problemie BIN PACKING. Użyj redukcji problemu PARTITION do pokazania, że nie istnieje algorytm \displaystyle a-aproksymacyjny. Skonstruuj rodzinę algorytmów \displaystyle \mathcal{A}_\epsilon pokrywających conajmniej \displaystyle (\braq{1 - \epsilon}) \textnormal{opt} pojemników przy pomocy grupowania, zaokrąglania i przeglądania wyczerpującego. Dzięki stałej \displaystyle c nie musisz się przejmować przedmiotami o wadze mniejszej niż \displaystyle \epsilon.

Rozwiązanie

Aby pokazać pierwszą część, wystarczy zauważyć, że jeżeli mamy instancję problemu PARTITION z elementami \displaystyle a_1,a_2,\ldots,a_n i sumą wag \displaystyle S=\sum_{i=1}^{n} s(a_i), to przy użyciu przedmiotów o wagach \displaystyle \frac{ s(a_1) }{S},\frac{ s(a_2) }{S},\ldots,\frac{ s(a_n) }{S} można pokryć \displaystyle 2 pojemniki tylko wtedy, kiedy da się elementy \displaystyle A rozbić na dwa podzbiory o tej samej wadze sumarycznej. Zatem algorytm \displaystyle a-aproksymacyjny dla \displaystyle a> \frac{1}{2} pozwoliłby rozstrzygać o problemie PARTITION.

Konstrukcja asymptotycznego PTAS przebiega dokładnie tak samo jak dla prolemu BIN PACKING.

Istnieje algorytm, który dla instancji z co najwyżej \displaystyle K różnymi wagami większymi niż \displaystyle \epsilon w czasie wielomianowym podaje rozwiązanie optymalne. Tak jak poprzednio można wtedy rozważyć wszystkie przypadki, których jest wielomianowo wiele.

Dla zadanego \displaystyle \epsilon i ograniczeniu instancji do zawierających przedmioty większe niż \displaystyle \epsilon możemy przeprowadzić taki sam podział przedmiotów na \displaystyle K=[\ceil{\frac{1}{\epsilon^2}}] grup tak, aby w każdej grupie było co najwyżej \displaystyle Q=[\floor{n\epsilon^2}] przedmiotów, a następnie zastosować algorytm dokładny dla zaokrągleń do najmniejszego przedmiotu w grupie.

Powtórzenie tej samej analizy pokazuje, że jest to algorytm \displaystyle (\braq{1-\epsilon})-aproksymacyjny.

Dodatkowe założenie o tym, że \displaystyle w_i > c, pozwala dla \displaystyle \epsilon < c,nie rozważać przedmiotów o wagach mniejszych od \displaystyle \epsilon. Jeżeli natomiast \displaystyle \epsilon > c, możemy użyć algorytmu \displaystyle \mathcal{A}_c.

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 5.1

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

  • Dla dowolnej instancji \displaystyle x problemu \displaystyle A zachodzi:
\textnormal{opt} \displaystyle  _B( R(x) )  \leq \alpha \cdot \textnormal{opt}\displaystyle  _A(x)\textnormal{.}
  • Dla dowolnego rozwiązania dopuszczalnego \displaystyle s instancji \displaystyle  R(x) zachodzi:
\displaystyle |\size{ \textnormal{opt} \displaystyle  _A(x)  -  \textnormal{obj}_A(x, S(s) ) }| \leq \beta  |\size{ \textnormal{opt} \displaystyle  _B( R(x) )  -  \textnormal{obj}_B( R(x) ,s) }|\textnormal{.}

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

Uwaga 5.2

Warto zauważyć, że definicja L-redukcji nie zależy od tego, czy problemy \displaystyle A i \displaystyle 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. \displaystyle R to po prostu funkcja identycznościowa na grafach, a \displaystyle 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ę \displaystyle k, to otrzymamy problemy \displaystyle k-INDPENDENT SET i \displaystyle k-VERTEX COVER. Przypomnijmy, że z redukcji problemu \displaystyle 3SAT wynika, że już problem \displaystyle 4-INDEPENDENT SET jest \displaystyle \cc{NP}-zupełny.

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

Zauważmy, że dla grafu \displaystyle G=(\braq{V,E}) ze stopniem wierzchołków ograniczonym przez \displaystyle k rozmiar maksymalnego zbioru niezależnego to co najmniej \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 \displaystyle 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 \displaystyle |\size{V}| elementów. W związku z tym możemy ustalić wartość parametru \displaystyle \alpha na \displaystyle k+1.

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

Ta krótka analiza pozwala stwierdzić, że para \displaystyle (\braq{R,S}) jest L-redukcją problemu \displaystyle k-INDEPENDENT SET do \displaystyle k-NODE COVER.

Można też skonstruować odwrotną L-redukcję problemu \displaystyle k-NODE COVER do \displaystyle k-INDEPENDENT SET. Oczywiście należy użyć tych samych funkcji \displaystyle R i \displaystyle 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 \displaystyle 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 \displaystyle R będzie usuwać wierzchołki izolowane z grafu (które i tak nie należą do minimalnego pokrycia wierzchołkowego). Funkcja \displaystyle S nadal będzie zamieniać zbiór wierzchołków na jego uzupełnienie (ale tylko w obrębie wierzchołków nieizolowanych). Rozmiar minimalnego pokrycia wierzchołkowego w grafie bez wierzchołków izolowanych wynosi co najmniej \displaystyle \frac{|\size{V}|}{k} ponieważ jest co najmniej \displaystyle |\size{V}| krawędzi, a każdy wierzchołek pokrywa co najwyżej \displaystyle k z nich. To oszacowanie pozwala nam stwierdzić, że nowa redukcja jest L-redukcją z parametrami \displaystyle k i \displaystyle 1.

Ćwiczenie 5.3

Złożenie L-redukcji.

Pokaż, że jeżeli para \displaystyle (\braq{R_1,S_1}) jest L-redukcją problemu \displaystyle \Pi_1 do \displaystyle \Pi_2, a para \displaystyle (\braq{R_2,S_2}) L-reduckją \displaystyle \Pi_2 do \displaystyle \Pi_3, to \displaystyle (\braq{R_1 \circ R_2, S_2 \circ S_1}) jest L-redukcją \displaystyle \Pi_1 do \displaystyle \Pi_3.

Wskazówka

Współczynniki nowej redukcji są iloczynami współczynników redukcji \displaystyle (\braq{R_1,S_1}) i \displaystyle (\braq{R_2,S_2}).

Rozwiązanie

Niech \displaystyle \alpha_1 i \displaystyle \beta_1 będą współczynnikami pierwszej redukcji, a \displaystyle \alpha_2 i \displaystyle \beta_2 drugiej. Zatem dla dowolnej instancji \displaystyle x problemu \displaystyle \Pi_1 zachodzi:

\displaystyle \textnormal{opt}_{\Pi_3}( R_2( R_1(x) ) )  \leq \alpha_2 \textnormal{opt}_{\Pi_2}( R_1(x) )  \leq \alpha_1 \alpha_2 \textnormal{opt}_{\Pi_1}(x)\textnormal{,}

Dla dowolnego rozwiązania dopuszczalnego \displaystyle s, dla \displaystyle  R_2( R_1(x) ) zachodzi:

\displaystyle |\size{ \textnormal{opt}_{\Pi_1}(x)  -  \textnormal{obj}_{\Pi_1}(x, S_1( S_2(s) ) ) }| \leq \beta_1 |\size{ \textnormal{opt}_{\Pi_2}( R_1(x) )  -  \textnormal{obj}_{\Pi_2}( R_1(x) , S_2(s) ) }| \leq \beta_1 \beta_2 |\size{ \textnormal{opt}\displaystyle_{\Pi_3}( R_2( R_1(x) ) )  -  \textnormal{obj}_{\Pi_3}( R_2( R_1(x) ) ,s) }|\textnormal{.}

Zatem skonstruowana redukcja jest L-redukcją z parametrami \displaystyle \alpha_1 \alpha_2 i \displaystyle \beta_1 \beta_2.

Ćwiczenie 5.4

Przenoszenie aproksymacji przez L-redukcje.

Pokaż, że jeżeli problem minimalizacyjny \displaystyle A L-redukuje się do problemu \displaystyle B i dla problemu \displaystyle B istnieje algorytm \displaystyle b-aproksymacyjny, to istnieje stała \displaystyle a taka, że dla problemu \displaystyle A istnieje algorytm \displaystyle a-aproksymacyjny.

Pokaż, że dla dowolnych problemów optymalizacyjnych \displaystyle A i \displaystyle B, że jeżeli \displaystyle A L-redukuje się do \displaystyle B i istnieje wielomianowy schemat aproksymacji dla problemu \displaystyle B, to istnieje też taki schemat dla problemu \displaystyle A.

Wskazówka

Przeprowadź instancję problemu \displaystyle A na instnację \displaystyle B, użyj algorytmu aproksymacyjnego i przeprowadź znalezione rozwiązanie z powrotem na wynik problemu \displaystyle A. Użyj ograniczeń \displaystyle \alpha i \displaystyle \beta do przeniesienia gwarancji aproksymacji.

Rozwiązanie

Niech \displaystyle (\braq{R,S}) będzie L-redukcją problemu \displaystyle A do \displaystyle B ze stałymi \displaystyle \alpha i \displaystyle \beta. Niech \displaystyle \mathcal{B} będzie \displaystyle b-aproksymacyjnym algorytmem dla problemu \displaystyle B. Skonstruujemy teraz algorytm \displaystyle \mathcal{A} dla problemu \displaystyle A, którego działanie dla dowolnej instancji \displaystyle x można opisać poprzez równanie:

\displaystyle  \mathcal{A}(x)  =  S( \mathcal{B}( R(x) ) )\textnormal{.}

Załóżmy, że \displaystyle B jest problemem maksymalizacyjnym. Fakt, że \displaystyle \mathcal{B} jest algorytmem \displaystyle b-aproksymacyjnym i własności L-redukcji gwarantują nam wtedy następujące nierówności:

\displaystyle \aligned  \textnormal{opt}_B( R(x) )  &\leq  \alpha \textnormal{opt}_A(x)  \\  \textnormal{obj}_B( R(x) , \mathcal{B}( R(x) ) )  &\geq  b \cdot \textnormal{opt}_B( R(x) )  \\  \textnormal{obj}_A(x, \mathcal{A}(x) )  -  \textnormal{opt}_A(x)  &\leq  \beta(\braq{  \textnormal{opt}_B( R(x) )  -  \textnormal{obj}_B( R(x) , \mathcal{B}( R(x) ) ) }) \textrm{, }  \endaligned

co po prostym przekształceniu daje:

\displaystyle  \textnormal{obj}_A(x, \mathcal{A}(x) )  \leq (\braq{1 + \alpha\beta(\braq{1-b})}) \textnormal{opt} \displaystyle  _A(x)

i pozwala stwierdzić, że \displaystyle \mathcal{A} jest algorytmem \displaystyle (\braq{1+\alpha\beta(\braq{1-b})})-aproksymacyjnym.

Jeżeli \displaystyle B jest problemem minimalizacyjnym to analogiczna analiza dowodzi, że \displaystyle \mathcal{A} jest algorytmem \displaystyle a-aproksymacyjnym dla \displaystyle a=1+\alpha\beta(\braq{b-1}).

Przeprowadzenie analogicznego rozumowania przy założeniu, że \displaystyle A jest problemem maksymalizacyjnym prowadzi do następujących nierówności:

\displaystyle  \textnormal{obj}_A(x, \mathcal{A}(x) )  \geq (\braq{1 - \alpha\beta(\braq{1-b})}) \textnormal{opt} \displaystyle  _A(x)\textnormal{,}

dla \displaystyle B maksymalizacyjnego i

\displaystyle  \textnormal{obj}_A(x, \mathcal{A}(x) )  \geq (\braq{1 - \alpha\beta(\braq{b-1})}) \textnormal{opt} \displaystyle  _A(x)\textnormal{,}

dla \displaystyle B minimalizacyjnego.

Te wyniki nie pozwalają przenieść gwarancji aproksymacji, gdyż otrzymane współczynniki mogą być ujemne, ale wszystkie cztery ograniczenia mają tę własność, że zmierzają do \displaystyle 1 przy \displaystyle b zmierzającym do \displaystyle 1. To pozwala przenieść PTAS dla problemu \displaystyle B na PTAS dla problemu \displaystyle A.

Ćwiczenie 5.5

Różnica optimum dla NODE COVER i INDEPENDENT SET.

Pokaż, że dla dowolnej liczby wymiernej \displaystyle q > 0 można skonstruować graf, dla którego iloraz rozmiaru maksymalnego zbioru niezależnego do minimalnego pokrycia wierzchołkowego wynosi \displaystyle q.

Rozwiązanie

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

Różnica optimum NC i IS

Przykładem grafu spełniającego warunki zadania dla liczby \displaystyle q=\frac{k}{l} jest graf składający się z \displaystyle k-1 elementowej antykliki i \displaystyle l+1 elementowej kliki. Rozmiar minimalnego pokrycia wierzchołkowego dla tego grafu to \displaystyle l, a największy zbiór niezależny ma \displaystyle k wierzchołków.

Klasa \displaystyle \cc{MAXSNP}

Wprowadzimy teraz formalną definicję klasy \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 \displaystyle \cc{MAXSNP}_0, która opisuje problemy maksymalizacyjne. Jej charakteryzacja jest analogiczna do charakteryzacji klasy \displaystyle \cc{NP} podanej w twierdzeniu Fagina.

Definicja 6.1

Problem \displaystyle A należy do klasy \displaystyle \cc{MAXSNP}_0, jeżeli można go wyrazić za pomocą formuły:

\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) }\}\textnormal{.}

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

Definicja 6.2

Klasa \displaystyle \cc{MAXSNP} jest domknięciem \displaystyle \cc{MAXSNP}_0 ze względu na L-redukcje.

Zobaczmy teraz przykład problemu, który należy do \displaystyle \cc{MAXSNP}_0. Wybierzemy problem \displaystyle 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 \displaystyle k+1-argumentową relację \displaystyle H. Każdemu wierzchołkowi \displaystyle G odpowiada jedna krotka relacji \displaystyle H - \displaystyle (\braq{x,y_1,y_2,\ldots,y_k}), która koduje sąsiedztwo wierzchołka \displaystyle x. Wierzchołki \displaystyle y_1,y_2,\ldots,y_k to sąsiedzi \displaystyle x. Jeżeli \displaystyle x nie ma \displaystyle k sąsiadów, to na brakujących pozycjach występuje \displaystyle x. Problem \displaystyle k-zbioru niezależnego koduje się wtedy w następujący sposób:

\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\textnormal{.}

Wybór relacji \displaystyle S koduje pewien podzbiór wierzchołków. Formuła kodująca problem jest spełniona dla krotek odpowiadających tym wierzchołkom \displaystyle 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 \displaystyle k-INDEPENDENT SET należy do klasy \displaystyle \cc{MAXSNP}_0. Natychmiastowym wnioskiem jest, że problem \displaystyle k-NODE COVER jest problemem z \displaystyle \cc{MAXSNP}. Znamy przecież jego L-redukcję do \displaystyle k-INDEPENDENT SET.

Ćwiczenie 6.3

MAX CUT w \displaystyle \cc{MAXSNP}.

Pokaż, że problem MAX CUT należy do \displaystyle \cc{MAXSNP}.

Wskazówka

Użyj zwykłej binarnej reprezentacji grafu do skonstruowania odpowiedniej formuły pokazującej, że MAX CUT należy do \displaystyle \cc{MAXSNP}_0.

Rozwiązanie

Formuła kodująca problem MAX CUT to:

\displaystyle \max_{S\subseteq V}\defset \{ {(\braq{x,y}) \in V^2} : {(\braq{x,y})\in G \wedge x \in S \wedge y \notin S} \}\textnormal{.}

Problemy MAXSAT i MAX FUNCTION SAT

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

Przypomnijmy, że na wejściu problemu MAXSAT dostajemy formułę logiczną w koniunkcyjnej postaci normalnej z \displaystyle 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.

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

Algorytm 7.1 [Algorytm wybierający wartościowanie \displaystyle x lub \displaystyle \overline{x}]


1. Wybierz dowolne wartościowanie \displaystyle x dla \displaystyle n zmiennych występujących w formule.

2. Skonstruuj wartościowanie \displaystyle \overline{x}, które przyporządkowuje zmiennym wartościowanie odwrotne do \displaystyle x.

3. Jako wynik podaj to z wartościowań \displaystyle x, \displaystyle \overline{x}, przy którym więcej klauzul jest spełnionych.

Twierdzenie 7.2

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

Dowód

Zauważmy, że jeżeli któraś z alternatyw jest niespełniona przy wartościowaniu \displaystyle x, to musi być spełniona przy wartościowaniu \displaystyle \overline{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 \displaystyle m - liczbę alternatyw w formule, przez \displaystyle c liczbę alternatyw spełnionych przy wartościowaniu \displaystyle x, a przez \displaystyle \overline{c} liczbę alternatyw spełnionych przy wartościowaniu \displaystyle \overline{x}, to zachodzą następującee nierówności:

\displaystyle \aligned c &\geq  m - \overline{c}\textnormal{,} \\ \overline{c} &\geq  m - c\textnormal{,} \\ c + \overline{c} &\geq  2m - c - \overline{c}\textnormal{,} \\ c + \overline{c} &\geq  m\textnormal{.} \endaligned

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

image:End_of_proof.gif

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

Problem

Problem maksymalnej spełnialności funkcyjnej MAX FUNCTION SAT.

Danych jest \displaystyle n zmiennych logicznych \displaystyle x_1,x_2,\ldots,x_n oraz \displaystyle m funkcji logicznych \displaystyle f_1,f_2,\ldots,f_m. Należy znaleźć wartościowanie zmiennych \displaystyle x_1,x_2,\ldots,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 \displaystyle k, to mamy do czynienia z problemem MAX\displaystyle kSAT i MAX\displaystyle kFSAT.

Przypomnijmy, iż pokazaliśmy, że już problem MAX\displaystyle 2SAT jest \displaystyle \cc{NP}-zupełny (mimo że problem \displaystyle 2SAT nie jest). Teraz okaże się, dlaczego te problemy są dla nas tak interesujące:

Twierdzenie 7.3

Problemy MAX\displaystyle kSAT należą do klasy \displaystyle \cc{MAXSNP}_0.

Dowód

Pokażemy, że problem MAX\displaystyle 2SAT należy do \displaystyle \cc{MAXSNP}_0. Konstrukcja reprezentacji formuły i kodowania problemu dla większych \displaystyle k jest analogiczna.

Zatem ustalamy, że uniwersum \displaystyle V to zbiór zmiennych występujących w formule, a trzy relacje binarne \displaystyle G_0,G_1,G_2 kodują formułę. Para \displaystyle (\braq{x_1,x_2}) w relacji \displaystyle G_i koduje wystąpienie klauzuli zawierającej literały \displaystyle x_1 i \displaystyle x_2, z których \displaystyle 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:

\displaystyle \aligned  G_0(x_i,x_j)  & \Longleftrightarrow & (\braq{\neg x_i \vee \neg x_j}); i < j\textnormal{,} \\  G_1(x_i,x_j)  & \Longleftrightarrow & (\braq{x_i \vee \neg x_j})\textnormal{,} \\  G_2(x_i,x_j)  & \Longleftrightarrow & (\braq{x_i \vee x_j}); i < j\textnormal{.} \endaligned

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

\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]} \}\textnormal{.}

Wybór relacji \displaystyle S odpowiada ustaleniu wartościowania, a konstrukcja formuły zapewnia, że liczba krotek \displaystyle (\braq{x,y}) spełniających formułę odpowiada liczbie alternatyw spełnionych przy danym wartościowaniu.

image:End_of_proof.gif


Drzewo wartościowań

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

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

\displaystyle  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}\textnormal{.}

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

\displaystyle  p(t,f_i)  = \frac{1}{2}(\braq{ p(t_0,f_i)  +  p(t_1,f_i) })\textnormal{.}

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

\displaystyle  P(t)  = \frac{1}{2}(\braq{ P(t_0)  +  P(t_1) })\textnormal{.}

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

Możemy już teraz przedstawić algorytm:

Algorytm 7.4 [Algorytm schodzący po drzewie wartościowań]


1. Ustaw zmienną \displaystyle t na korzeń \displaystyle r drzewa wartościowań.

2. Dopóki \displaystyle t nie będzie liściem drzewa wartościowań:

obliczaj wartość \displaystyle  P(t_0) i \displaystyle  P(t_1) dla dzieci węzła \displaystyle t

i ustaw \displaystyle t na to z dzieci, dla którego wartość \displaystyle  P(t_i) jest większa.

3. Podaj wartościowanie opisywane przez węzeł \displaystyle t jako wynik.

Twierdzenie 7.5

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

Dowód

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

Zauważmy, że \displaystyle  P(t)  \geq  P(r). Jest tak dlatego, że przy każdym zejściu w dół drzewa od węzła \displaystyle s jest spełnione \displaystyle  P(s)  = \frac{1}{2}(\braq{ P(s_0)  +  P(s_1) }), więc któraś z wartości \displaystyle  P(s_0), lub \displaystyle  P(s_1) jest większa lub równa \displaystyle  P(s), a algorytm wybiera zejście w kierunku większej z nich. W związku z tym wartość funkcji \displaystyle 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ż \displaystyle [\ceil{ P(r) }]. Ponieważ dla każdej funkcji, która może w ogóle dać wynik pozytywny, przy jakimkolwiek wartościowaniu zachodzi \displaystyle  p(r,f_i)  \geq \frac{1}{2^k}, to liczba funkcji, które dają wynik pozytywny w rozwiązaniu optymalnym, jest ograniczona z góry przez \displaystyle \frac{ P(r) }{\frac{1}{2^k}}. To dowodzi, że algorytm jest algorytmem \displaystyle \frac{1}{2^k}-aproksymacyjnym.

image:End_of_proof.gif

Ćwiczenie 7.6

Kodowanie MAX\displaystyle kFSAT w MAX\displaystyle 3SAT.

Pokaż L-redukcję problemu MAX\displaystyle kFSAT do MAX\displaystyle 3SAT.

Wskazówka

Użyj reprezentacji funkcji logicznej przez układ bramek logicznych, a następnie przedstaw każdą bramkę jako klauzulę \displaystyle 3SAT.

Rozwiązanie

Dla wygody załóżmy, że żadna z funkcji nie przyjmuje stale wartości negatywnej. Gdyby któraś z nich miała taką własność, to możemy to rozpoznać i usunąć ją z instancji problemu.

Skorzystamy teraz z tego, że każdą funkcję logiczną można przedstawić jako układ bramek logicznych zbudowany z bramek:

  • wejściowych,
  • negacji (\displaystyle \neg),
  • koniunkcji (\displaystyle \wedge),
  • alternatywy (\displaystyle \vee),
  • jednej bramki wyjściowej.

Skonstruowana formuła \displaystyle 3SAT będzie modelować układ takich bramek. Zmienne formuły będą odpowiadać bramkom i zmiennym występującym w modelowanej funkcji. Dla każdej bramki wejściowej \displaystyle g dodajemy klauzule:

  • \displaystyle (\braq{g \vee \neg x}) \wedge (\braq{\neg g \vee x}) jeżeli bramka \displaystyle g odpowiada zmiennej \displaystyle x.
  • \displaystyle (\braq{g}) lub \displaystyle (\braq{\neg g}) jeżeli bramka \displaystyle g ma stałą wartość logiczną.

Dalej, konstrukcja dla bramek operatorów logicznych jest następująca:

  • \displaystyle (\braq{g \vee a}) \wedge (\braq{\neg g \vee \neg a}) bramka \displaystyle g odpowiadająca operacji \displaystyle \neg z wejściem z bramki \displaystyle a.
  • \displaystyle (\braq{g \vee \neg a}) \wedge (\braq{g \vee \neg b}) \wedge (\braq{\neg b \vee a \vee b}) bramka \displaystyle g odpowiadająca operacji \displaystyle \vee z wejściami z bramek \displaystyle a i \displaystyle b.
  • \displaystyle (\braq{\neg g \vee a}) \wedge (\braq{\neg g \vee b}) \wedge (\braq{g \vee \neg a \vee \neg b}) bramka \displaystyle g odpowiadająca operacji \displaystyle \wedge z wejściami z bramek \displaystyle a i \displaystyle b.

Dla bramki wyjściowej \displaystyle g dodajemy jedną klauzulę \displaystyle (\braq{g}). W tak skonstruowanej formule wszystkie klauzule mogą być spełnione, być może z wyjątkiem ostatniej. Wystarczy zauważyć, że w każdej dodanej grupie mogą być spełnione wszystkie klauzule, o ile wartościowania są "zgodne" z zachowaniem bramki.

Możemy zatem zamienić wszystkie funkcje logiczne występujące w problemie MAX\displaystyle kFSAT na formuły MAX\displaystyle 3SAT. Optimum tego drugiego problemu będzie równe ilości wszystkich bramek poza wyjściowymi zwiększonym o liczbę funkcji, które mogą jednocześnie dawać wynik pozytywny. Stąd możemy ustalić współczynnik \displaystyle \beta redukcji na \displaystyle 1.

Żeby uzasadnić, że optimum w skonstruowanej formule jest ograniczone liniowo od optimum problemu MAX\displaystyle kFSAT, przypomnijmy dowód dla algorytmu aproksymacyjnego dla problemu MAX\displaystyle kFSAT. Pokazaliśmy tam, że optimum problemu wynosi co najmniej \displaystyle \frac{1}{2^k}m, gdzie \displaystyle m jest liczbą funkcji. Tymczasem liczba klauzul zależy liniowo od liczby funkcji. Skonstruowana redukcja jest zatem L-redukcją.

Ćwiczenie 7.7

Lepsza aproksymacja MAXSAT.

Pokaż, że jeżeli wymagalibyśmy od instancji problemu MAXSAT, aby w każdej alternatywie występowało przynajmniej \displaystyle k literałów, to istnieje algorytm \displaystyle (\braq{1-\frac{1}{2^k}})-aproksymacyjny dla takiego problemu.

Wskazówka

Jak wygląda oszacowanie \displaystyle  P(r,f_i), gdy \displaystyle f_i reprezentuje klauzulę?

Rozwiązanie

Wystarczy zauważyć, że jeżeli \displaystyle f_i reprezentuje klauzulę z \displaystyle j literałami, to \displaystyle  P(r,f_i) =1-\frac{1}{2^j}, gdyż jest tylko jedno wartościowanie występujących w niej zmiennych, które jej nie spełnia. Możemy w związku z tym powtórzyć rozumowanie z dowodu aproksymacji problemu MAX\displaystyle kFSAT i podany tam algorytm w tym wypadku jest algorytmem \displaystyle (\braq{1-\frac{1}{2^k}})-aproksymacyjnym.

Problemy \displaystyle \cc{MAXSNP}-zupełne

Pokażemy teraz, że problem MAX\displaystyle 3SAT jest problemem zupełnym w sensie L-redukcji w klasie \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 \displaystyle \cc{MAXSNP}. Jest też to fakt interesujący ze względu na to, że wcale nie jest oczywiste, iż problemy \displaystyle \cc{MAXSNP}-zupełne muszą w ogóle istnieć.

Twierdzenie 8.1

MAX\displaystyle 3SAT jest problemem zupełnym w sensie L-redukcji w klasie \displaystyle \cc{MAXSNP}.

Dowód

Przypomnijmy, że klasa \displaystyle \cc{MAXSNP} jest definiowana jako klasa problemów L-redukowalnych do problemów z \displaystyle \cc{MAXSNP}_0. Zatem wystarczy, że pokażemy, iż każdy problem z \displaystyle \cc{MAXSNP}_0 jest L-redukowalny do problemu MAX\displaystyle 3SAT i skorzystamy z tego, że złożenie L-redukcji jest L-redukcją.

Rozważmy zatem problem \displaystyle A z klasy \displaystyle \cc{MAXSNP}_0 definiowany formułą:

\displaystyle \max_S\defset \{ {(\braq{x_1,x_2,\ldots,x_k})} : {\phi} \}\textnormal{.}

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

Możemy teraz spojrzeć na rozwiązanie tej instancjii problemu \displaystyle A jak na ustalenie wartościowania formuł \displaystyle  S(v_{i_1},v_{i_2},\ldots,v_{i_r}), tak aby zmaksymalizować liczbę spełnionych formuł \displaystyle \phi_v. Jeżeli któraś z formuł \displaystyle \phi_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 \displaystyle A do problemu MAX\displaystyle lFSAT, gdzie jest \displaystyle |\size{V}|^r zmiennych odpowiadających \displaystyle  S(v_{i_1},v_{i_2},\ldots,v_{i_r}) i \displaystyle |\size{V}|^r funkcji logicznych odpowiadających formułom \displaystyle \phi_v. Stała \displaystyle l zależy tylko od postaci formuły \displaystyle \phi i należy ją ustalić równą liczbie wystąpień symbolu relacyjnego \displaystyle S w formule \displaystyle \phi. Możemy teraz użyć redukcji MAX\displaystyle lFSAT do MAX\displaystyle 3SAT.

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

Musimy teraz skorzystać z pewnych własności problemu MAX\displaystyle lFSAT i jego redukcji do MAX\displaystyle 3SAT.

Po pierwsze, każda formuła \displaystyle \phi_v jest reprezentowana przez co najwyżej \displaystyle c klauzul, gdzie \displaystyle c zależy tylko od liczby bramek potrzebnych do wyrażenia formuły \displaystyle \phi.

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

Po trzecie, zastosowana redukcja MAX\displaystyle lFSAT do MAX\displaystyle 3SAT gwarantuje, że w rozwiązaniu optymalnym problemu \displaystyle  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 \displaystyle \alpha = \frac{c}{d}( \textnormal{opt} \displaystyle  (x)  \geq dm, \textnormal{opt} \displaystyle  ( R(x) )  \leq cm) i \displaystyle \beta = 1 (w rozwiązaniu optymalnym \textnormal{opt} problemu \displaystyle  R(x) liczba spełnionych alternatyw zmniejszona o liczbę alternatyw innych niż przechowujące wyniki funkcji wyznacza dokładnie liczbę krotek \displaystyle V^k, dla których relacja \displaystyle S zachodzi).

image:End_of_proof.gif

Ćwiczenie 8.2

Problemy z \displaystyle \cc{MAXSNP}_0 są aproksymowalne ze stałą.

Pokaż, że dla każdego problemu z klasy \displaystyle \cc{MAXSNP} istnieje algorytm \displaystyle a-aproksymacyjny dla pewnej stałej.

Wskazówka

Wykorzystaj technikę użytą w dowodzie \displaystyle \cc{MAXSNP}-zupełności problemu MAX\displaystyle 3SAT.

Rozwiązanie

W dowodzie \displaystyle \cc{MAXSNP}-zupełności problemu MAX\displaystyle 3SAT pokazaliśmy, że na każdy problem \displaystyle A z klasy \displaystyle \cc{MAXSNP}_0 można patrzeć jak na problem MAX\displaystyle kFSAT dla pewnego \displaystyle k. Tymczasem pokazaliśmy wcześniej, że problem MAX\displaystyle kFSAT może być aproksymowany ze stałą \displaystyle \frac{1}{2^k}, co przenosi się bezpośrednio na taką samą aproksymację dla problemu \displaystyle A.

Testy końcowe