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

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ę $\mathrm {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 ${\mathcal {A}}$ jest {schematem aproksymacji} dla problemu $\mathrm {NP}$-optymalizacyjnego $\Pi$, jeżeli dla wejścia $({\mathit {I,\epsilon }})$, gdzie $I$ jest instancją problemu $\Pi$, a $\epsilon >0$ opisuje dopuszczalny błąd, znajduje rozwiązanie takie, że:

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

Definicja 2.2

Jeśli dla dowolnego $\epsilon >0$ czas działania ${\mathcal {A}}$ na wejściu $({\mathit {I,\epsilon }})$ jest wielomianowy względem $|{\mathit {I}}|$, to ${\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 $\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 ${\mathcal {A}}$ jest wielomianowy względem $|{\mathit {I}}|$ oraz wartości ${\frac {1}{\epsilon }}$, to ${\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 $\mathrm {NP}$-zupełnych.

Wykaż, że o ile $\mathrm {P} \neq \mathrm {NP}$ i $\Pi$ jest silnie $\mathrm {NP}$-zupełnym problemem optymalizacyjnym takim, że funkcja celu ${\text{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 $\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 $\mathrm {NP}$-zupełnej decyzyjnej wersji problemu $\Pi$.

Rozwiązanie

Niech $\Pi$ będzie problemem maksymalizacji z funkcją celu ${\text{obj}}_{\Pi }$ (dla problemu minimalizacji dowód przebiega analogicznie). Załóżmy, że jej wartości są całkowite dodatnie oraz dla każdej instancji $I$, ${\text{obj}}_{\Pi }(I)<p(|I|,NUM(I))$, gdzie $p$ jest pewnym wielomianem dwóch zmiennych, a Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle NUM(I)} jest skojarzoną z problemem funkcją określającą wartość największej liczby występującej w instancji. Załóżmy, że Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A} jest FPTAS dla Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Pi} . Skonstruujemy algorytm pseudowielomianowy dla Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Pi} .

Na wejściu dana jest instancja Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle I} . Algorytm składa sie z dwóch kroków:

1. oblicz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \delta = 1/p(|I|,NUM(I))} ,

2. zastosuj Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle A} dla instancji Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle I} i dokładności Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \delta} obliczone rozwiązanie dopuszczalne Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle S} wypisz na wyjście.

Ponieważ Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Pi} jest maksymalizacyjny, więc Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \text{obj}_\Pi(I,S)\geq (1-\delta)} . Zatem Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \text{opt}(I)-\text{obj}_\Pi(I,S) \leq \delta \, \text{opt}(I) < 1} .

Z tego, że wartości funkcji celu są całkowitoliczbowe, wynika Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \text{obj}_\Pi(I,S)=\text{opt}(I)} , a zatem nasz algorytm znajduje rozwiązania optymalne. Zgodnie z definicją FPTAS, algorytm działa w czasie wielomianowym od Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle |I|} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 1/\delta} , jest to więc algorytm pseudowielomianowy dla Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Pi} .

Z analizowanych w poprzednim wykładzie własności silnej NP-zupełności wynika, że musi to być algorytm wielomianowy dla $\Pi$, co oczywiście jest sprzeczne z założeniem $\mathrm {P} \neq \mathrm {NP}$.

Schemat aproksymacji dla problemu KNAPSACK

Pokazaliśmy, że nie warto szukać algorytmów FPTAS dla problemów silnie $\mathrm {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 $\mathrm {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 $V=\max _{i=1,2,\ldots ,n}v(a_{i})$.

2. Oblicz $W_{i,u}$ określone dla $0\leq i\leq n$ i $0\leq u\leq nV$ jako "minimalny sumaryczny rozmiar podzbioru przedmiotów $S\subseteq {a_{1},a_{2},\ldots ,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: ${\begin{aligned}W_{0,u}&=\infty {\text{,}}\\W_{i+1,u}&=\min(W_{i,u},W_{i,u-v(a_{i+1})}+w(a_{i+1})){\text{.}}\end{aligned}}$

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

Algorytm ten można zakodować tak, aby znajdował optymalne rozwiązanie w czasie ${\mathcal {O}}({n^{2}V})$. 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}{\epsilon }}$. Oto algorytm:

Algorytm 3.2 [Algorytm zaokrągleniowy]

---

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

2. Dla każdego przedmiotu oblicz $v'(a_{i})=[{\frac {v(a_{i})}{K}}]$.

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

Twierdzenie 3.3

Algorytm zaokrągleniowy jest FPTAS dla problemu plecakowego.

Dowód

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

$\sum _{i\in S}v(a_{i})\geq ({\mathit {1-\epsilon }}){\text{opt}}{\text{.}}$

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

$\sum _{i\in S}v(a_{i})\geq \sum _{i\in S}[{\frac {v(a_{i})}{K}}]K\geq \sum _{i\in O}[{\frac {v(a_{i})}{K}}]K\geq \sum _{i\in O}({\mathit {v(a_{i}))-K}}\geq \sum _{i\in O}v(a_{i})-nK{\text{.}}$

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 $|{\mathit {S}}|\leq n$.

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

Ćwiczenie 3.4

Algorytm pseudowielomianowy.

Doprecyzuj implementację algorytmu pseudowielomianowego dla problemu plecakowego. Jak odzyskać wybór przedmiotów z tablicy $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ę $W_{i,u}$:

for $u=0,1,\ldots ,V$ do
  $W_{0,u}=\infty$
end for
for $i=1,2,\ldots ,n$ do
  for $u=0,1,\ldots ,nV$ do
    $W_{i,u}=W_{i-1,u}$
    if $u-v(a_{i})\geq 0$ and $W_{i-1,u-v(a_{i})}+w(a_{i})<W_{i,u}$ then
      $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:

$S=\emptyset$
$o=0$
for $u=0,1,\ldots ,nV$ do
  if $W_{n,u}\leq B$
    $o=u$
  end if
end for
$i=n$
while $o>0$ do
  if $W_{i,o}=W_{i-1,o}$ then
    $i=i-1$ 
  else
    $S=S\cup \{i\}$
    $o=o-v(a_{i})$
    $i=i-1$
  end if
end while
return $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 $\mathrm {NP}$-zupełny i o ile $\mathrm {P} \neq \mathrm {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 $\mathrm {P} \neq \mathrm {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 ${\mathcal {A}}_{\epsilon }$ dla $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 $({\mathit {1+2\epsilon }}){\text{opt}}+1$ pojemników.

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

Lemat 4.1

Dla dowolnego $\epsilon >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ż $\epsilon$.

Dowód

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

Liczba możliwych zawartości jednego pojemnika jest zatem ograniczona przez $R={\binom {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 $\epsilon$.

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={\binom {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 wielomianowym przejrzeć wszystkie rozwiązania dopuszczalne i wybrać optymalne.

Uwaga 4.2

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 4.3

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

Dowód

Algorytm 4.4 [Algorytm dzielący na grupy]

---

1. Oblicz $K=[{\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 $Q=[{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ż $\epsilon$.

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 ${\text{opt}}(I^{*})\leq ({\mathit {1+\epsilon }}){\text{opt}}(I)$. Łatwo jest uzasadnić oszacowanie ${\text{opt}}(I_{*})\leq {\text{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:

${\text{opt}}(I^{*})\leq {\text{opt}}(I_{*})+Q\leq {\text{opt}}(I)+Q\leq {\text{opt}}(I)+[{n\epsilon ^{2}}]\leq ({\mathit {1+\epsilon }}){\text{opt}}(I){\text{.}}$

Ostatnia nierówność wynika z tego, że $n\epsilon \leq {\text{opt}}(I)$. Pokazaliśmy zatem, że algorytm jest $({\mathit {1+\epsilon }})$-aproksymacyjny.

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

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

---

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

2. Oblicz instancję $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 $\epsilon$ za pomocą algorytmu First-Fit, otrzymując rozwiązanie dla instancji wejściowej $I$.

Twierdzenie 4.6

Dla dowolnego $0<\epsilon \leq {\frac {1}{2}}$ algorytm ${\mathcal {A}}_{\epsilon }$ znajduje upakowanie przedmiotów instancji $I$ w co najwyżej $({\mathit {1+2\epsilon }}){\text{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_{\geq \epsilon }$ używa $({\mathit {1+\epsilon }}){\text{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-\epsilon$. 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 $({\mathit {M-1}})({\mathit {1-\epsilon }})$. W związku z tym możemy napisać:

$M\leq {\frac {{\text{opt}}(I)}{1-\epsilon }}+1\leq ({\mathit {1+2\epsilon }}){\text{opt}}(I)+1{\text{.}}$

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

Ćwiczenie 4.7

Aproksymacja dla problemu PARTITION.

Optymalizacyjna wersja problemu PARTITION powstaje, kiedy chcemy wybrać podzbiór $A'\subseteq A$ taki, że minimalizuje wartość $|{\mathit {\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 $A'\subseteq A$ taki, że iloraz:

${\frac {\sum _{a\in A'}s(a)}{\sum _{a\in A\setminus A'}s(a)}}\geq 1{\text{,}}$

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

Pokaż algorytm FPTAS dla tej wersji problemu PARTITION.

Wskazówka

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

Żeby skonstruować FPTAS dla drugiego problemu, załóżmy, że $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 $T=\sum _{i=1}^{n}s(a_{i})$ i $K={\frac {\epsilon T}{4n}}$ i znajdując rozwiązanie dokładne przy $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 $A'$ znaleziony przy wagach $s'$ nie jest rozwiązaniem dopuszczalnym przy wagach $s$, gdyż ${\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 $s$. Z problemem tym możemy sobie na szczęście łatwo poradzić, zamieniając znaleziony zbiór $A'$ na $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 $O$ jest rozwiązaniem optymalnym:

${\frac {T}{2}}\leq \sum _{a\in A'}s(a)\leq \sum _{a\in A'}[{\frac {s(a)+K}{K}}]K\leq \sum _{a\in O}[{\frac {s(a)}{K}}]K+Kn\leq {\text{opt}}+2Kn\leq {\text{opt}}+\epsilon {\frac {T}{2}}\leq ({\mathit {1+\epsilon }}){\text{opt}}{\text{.}}$

Przy przekształceniach korzystamy z własności zaokrągleń, a ostatnia nierówność wynika z tego, że ${\text{opt}}\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 $n$ przedmiotów o wagach wymiernych $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ć $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 $\mathrm {P} \neq \mathrm {NP}$, to nie ma dla niego algorytmu $a$-aproksymacyjnego dla $a>{\frac {1}{2}}$. Skonstruuj asymptotyczny PTAS przy dodatkowym założeniu, że rozmiary wszystkich przedmiotów są większe niż pewna stała $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 $a$-aproksymacyjny. Skonstruuj rodzinę algorytmów ${\mathcal {A}}_{\epsilon }$ pokrywających conajmniej $({\mathit {1-\epsilon }}){\text{opt}}$ pojemników przy pomocy grupowania, zaokrąglania i przeglądania wyczerpującego. Dzięki stałej $c$ nie musisz się przejmować przedmiotami o wadze mniejszej niż $\epsilon$.

Rozwiązanie

Aby pokazać pierwszą część, wystarczy zauważyć, że jeżeli mamy instancję problemu PARTITION z elementami $a_{1},a_{2},\ldots ,a_{n}$ i sumą wag $S=\sum _{i=1}^{n}s(a_{i})$, to przy użyciu przedmiotów o wagach ${\frac {s(a_{1})}{S}},{\frac {s(a_{2})}{S}},\ldots ,{\frac {s(a_{n})}{S}}$ można pokryć $2$ pojemniki tylko wtedy, kiedy da się elementy $A$ rozbić na dwa podzbiory o tej samej wadze sumarycznej. Zatem algorytm $a$-aproksymacyjny dla $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 $K$ różnymi wagami większymi niż $\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 $\epsilon$ i ograniczeniu instancji do zawierających przedmioty większe niż $\epsilon$ możemy przeprowadzić taki sam podział przedmiotów na $K=[{\frac {1}{\epsilon ^{2}}}]$ grup tak, aby w każdej grupie było co najwyżej $Q=[{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 $({\mathit {1-\epsilon }})$-aproksymacyjny.

Dodatkowe założenie o tym, że $w_{i}>c$, pozwala dla $\epsilon <c$,nie rozważać przedmiotów o wagach mniejszych od $\epsilon$. Jeżeli natomiast $\epsilon >c$, możemy użyć algorytmu ${\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 $A$ i $B$, parę funkcji $R:D_{A}\rightarrow D_{B}$ i $S:S_{B}\rightarrow 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:

${\text{opt}}_{B}(R(x))\leq \alpha \cdot {\text{opt}}_{A}(x){\text{.}}$

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

$|{\mathit {{\text{opt}}_{A}(x)-{\text{obj}}_{A}(x,S(s))}}|\leq \beta |{\mathit {{\text{opt}}_{B}(R(x))-{\text{obj}}_{B}(R(x),s)}}|{\text{.}}$

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 5.2

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 $\mathrm {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 $G=({\mathit {V,E}})$ ze stopniem wierzchołków ograniczonym przez $k$ rozmiar maksymalnego zbioru niezależnego to co najmniej ${\frac {|{\mathit {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 $|{\mathit {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 $({\mathit {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 nieizolowanych). Rozmiar minimalnego pokrycia wierzchołkowego w grafie bez wierzchołków izolowanych wynosi co najmniej ${\frac {|{\mathit {V}}|}{k}}$ ponieważ jest co najmniej $|{\mathit {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 5.3

Złożenie L-redukcji.

Pokaż, że jeżeli para $({\mathit {R_{1},S_{1}}})$ jest L-redukcją problemu $\Pi _{1}$ do $\Pi _{2}$, a para $({\mathit {R_{2},S_{2}}})$ L-reduckją $\Pi _{2}$ do $\Pi _{3}$, to $({\mathit {R_{1}\circ R_{2},S_{2}\circ S_{1}}})$ jest L-redukcją $\Pi _{1}$ do $\Pi _{3}$.

Wskazówka

Współczynniki nowej redukcji są iloczynami współczynników redukcji $({\mathit {R_{1},S_{1}}})$ i $({\mathit {R_{2},S_{2}}})$.

Rozwiązanie

Niech $\alpha _{1}$ i $\beta _{1}$ będą współczynnikami pierwszej redukcji, a $\alpha _{2}$ i $\beta _{2}$ drugiej. Zatem dla dowolnej instancji $x$ problemu $\Pi _{1}$ zachodzi:

${\text{opt}}_{\Pi _{3}}(R_{2}(R_{1}(x)))\leq \alpha _{2}{\text{opt}}_{\Pi _{2}}(R_{1}(x))\leq \alpha _{1}\alpha _{2}{\text{opt}}_{\Pi _{1}}(x){\text{,}}$

Dla dowolnego rozwiązania dopuszczalnego $s$, dla $R_{2}(R_{1}(x))$ zachodzi:

$|{\mathit {{\text{opt}}_{\Pi _{1}}(x)-{\text{obj}}_{\Pi _{1}}(x,S_{1}(S_{2}(s)))}}|\leq \beta _{1}|{\mathit {{\text{opt}}_{\Pi _{2}}(R_{1}(x))-{\text{obj}}_{\Pi _{2}}(R_{1}(x),S_{2}(s))}}|\leq \beta _{1}\beta _{2}|{\mathit {{\text{opt}}_{\Pi _{3}}(R_{2}(R_{1}(x)))-{\text{obj}}_{\Pi _{3}}(R_{2}(R_{1}(x)),s)}}|{\text{.}}$

Zatem skonstruowana redukcja jest L-redukcją z parametrami $\alpha _{1}\alpha _{2}$ i $\beta _{1}\beta _{2}$.

Ćwiczenie 5.4

Przenoszenie aproksymacji przez L-redukcje.

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

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

Wskazówka

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

Rozwiązanie

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

${\mathcal {A}}(x)=S({\mathcal {B}}(R(x))){\text{.}}$

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

${\begin{aligned}{\text{opt}}_{B}(R(x))&\leq \alpha {\text{opt}}_{A}(x)\\{\text{obj}}_{B}(R(x),{\mathcal {B}}(R(x)))&\geq b\cdot {\text{opt}}_{B}(R(x))\\{\text{obj}}_{A}(x,{\mathcal {A}}(x))-{\text{opt}}_{A}(x)&\leq \beta ({\mathit {{\text{opt}}_{B}(R(x))-{\text{obj}}_{B}(R(x),{\mathcal {B}}(R(x)))}}){\text{, }}\end{aligned}}$

co po prostym przekształceniu daje:

${\text{obj}}_{A}(x,{\mathcal {A}}(x))\leq ({\mathit {1+\alpha \beta ({\mathit {1-b}})}}){\text{opt}}_{A}(x)$

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

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

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

${\text{obj}}_{A}(x,{\mathcal {A}}(x))\geq ({\mathit {1-\alpha \beta ({\mathit {1-b}})}}){\text{opt}}_{A}(x){\text{,}}$

dla $B$ maksymalizacyjnego i

${\text{obj}}_{A}(x,{\mathcal {A}}(x))\geq ({\mathit {1-\alpha \beta ({\mathit {b-1}})}}){\text{opt}}_{A}(x){\text{,}}$

dla $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 $1$ przy $b$ zmierzającym do $1$. To pozwala przenieść PTAS dla problemu $B$ na PTAS dla problemu $A$.

Ćwiczenie 5.5

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

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

Rozwiązanie

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

Klasa $\mathrm {MAXSNP}$

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

Definicja 6.1

Problem $A$ należy do klasy $\mathrm {MAXSNP} _{0}$, jeżeli można go wyrazić za pomocą formuły:

$\max _{S}{\{({\mathit {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})}\}{\text{.}}$

Wejściem dla problemu $A$ jest ciąg relacji (być może wieloargumentowych) $G_{i},i=1,2,\ldots ,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 $\phi$ jest spełniona.

Definicja 6.2

Klasa $\mathrm {MAXSNP}$ jest domknięciem $\mathrm {MAXSNP} _{0}$ ze względu na L-redukcje.

Zobaczmy teraz przykład problemu, który należy do $\mathrm {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$ - $({\mathit {x,y_{1},y_{2},\ldots ,y_{k}}})$, która koduje sąsiedztwo wierzchołka $x$. Wierzchołki $y_{1},y_{2},\ldots ,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:

${\begin{aligned}\max _{S\subseteq V}\{({\mathit {x,y_{1},y_{2},\ldots ,y_{k}}})\in V^{k}:({\mathit {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]\}\end{aligned}}{\text{.}}$

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 $\mathrm {MAXSNP} _{0}$. Natychmiastowym wnioskiem jest, że problem $k$-NODE COVER jest problemem z $\mathrm {MAXSNP}$. Znamy przecież jego L-redukcję do $k$-INDEPENDENT SET.

Ćwiczenie 6.3

MAX CUT w $\mathrm {MAXSNP}$.

Pokaż, że problem MAX CUT należy do $\mathrm {MAXSNP}$.

Wskazówka

Użyj zwykłej binarnej reprezentacji grafu do skonstruowania odpowiedniej formuły pokazującej, że MAX CUT należy do $\mathrm {MAXSNP} _{0}$.

Rozwiązanie

Formuła kodująca problem MAX CUT to:

$\max _{S\subseteq V}\{{({\mathit {x,y}})\in V^{2}}:{({\mathit {x,y}})\in G\wedge x\in S\wedge y\notin S}\}{\text{.}}$

Problemy MAXSAT i MAX FUNCTION SAT

Problem maksymalnej spełnialności MAXSAT i jego zawężenia pełnią podobną rolę dla klasy $\mathrm {MAXSNP}$ jak problem SAT dla $\mathrm {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 $\mathrm {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 7.1 [Algorytm wybierający wartościowanie $x$ lub ${\overline {x}}$]

---

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

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

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

Twierdzenie 7.2

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 ${\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 $m$ - liczbę alternatyw w formule, przez $c$ liczbę alternatyw spełnionych przy wartościowaniu $x$, a przez ${\overline {c}}$ liczbę alternatyw spełnionych przy wartościowaniu ${\overline {x}}$, to zachodzą następującee nierówności:

${\begin{aligned}c&\geq m-{\overline {c}}{\text{,}}\\{\overline {c}}&\geq m-c{\text{,}}\\c+{\overline {c}}&\geq 2m-c-{\overline {c}}{\text{,}}\\c+{\overline {c}}&\geq m{\text{.}}\end{aligned}}$

Ponieważ algorytm wybiera to z wartościowań $x$ lub ${\overline {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},\ldots ,x_{n}$ oraz $m$ funkcji logicznych $f_{1},f_{2},\ldots ,f_{m}$. Należy znaleźć wartościowanie zmiennych $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 $k$, to mamy do czynienia z problemem MAX$k$SAT i MAX$k$FSAT.

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

Twierdzenie 7.3

Problemy MAX$k$SAT należą do klasy $\mathrm {MAXSNP} _{0}$.

Dowód

Pokażemy, że problem MAX$2$SAT należy do $\mathrm {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 $({\mathit {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:

${\begin{aligned}G_{0}(x_{i},x_{j})&\Longleftrightarrow &({\mathit {\neg x_{i}\vee \neg x_{j}}});i<j{\text{,}}\\G_{1}(x_{i},x_{j})&\Longleftrightarrow &({\mathit {x_{i}\vee \neg x_{j}}}){\text{,}}\\G_{2}(x_{i},x_{j})&\Longleftrightarrow &({\mathit {x_{i}\vee x_{j}}});i<j{\text{.}}\end{aligned}}$

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

$\max _{S\subseteq V}\{{({\mathit {x,y}})}:{\left[G_{0}(x,y)\wedge ({\mathit {\neg S(x)\vee \neg S(y)}})\right]\vee \left[G_{1}(x,y)\wedge ({\mathit {S(x)\vee \neg S(y)}})\right]\vee \left[G_{2}(x,y)\wedge ({\mathit {S(x)\vee S(y)}})\right]}\}{\text{.}}$

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

Drzewo wartościowań

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},\ldots ,x_{n}$ i $m$ funkcji logicznych $f_{1},f_{2},\ldots ,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 (rysunek Drzewo wartościowań).

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

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

$p(t,f_{i})={\frac {1}{2}}({\mathit {p(t_{0},f_{i})+p(t_{1},f_{i})}}){\text{.}}$

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

$P(t)={\frac {1}{2}}({\mathit {P(t_{0})+P(t_{1})}}){\text{.}}$

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 7.4 [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.

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

Twierdzenie 7.5

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)\geq P(r)$. Jest tak dlatego, że przy każdym zejściu w dół drzewa od węzła $s$ jest spełnione $P(s)={\frac {1}{2}}({\mathit {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ż $[{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})\geq {\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 7.6

Kodowanie MAX$k$FSAT w MAX$3$SAT.

Pokaż L-redukcję problemu MAX$k$FSAT do MAX$3$SAT.

Wskazówka

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

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 ($\neg$),
• koniunkcji ($\wedge$),
• alternatywy ($\vee$),
• jednej bramki wyjściowej.

Skonstruowana formuła $3$SAT 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 $g$ dodajemy klauzule:

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

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

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

Dla bramki wyjściowej $g$ dodajemy jedną klauzulę $({\mathit {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$k$FSAT na formuły MAX$3$SAT. 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 $\beta$ redukcji na $1$.

Żeby uzasadnić, że optimum w skonstruowanej formule jest ograniczone liniowo od optimum problemu MAX$k$FSAT, przypomnijmy dowód dla algorytmu aproksymacyjnego dla problemu MAX$k$FSAT. Pokazaliśmy tam, że optimum problemu wynosi co najmniej ${\frac {1}{2^{k}}}m$, gdzie $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 $k$ literałów, to istnieje algorytm $({\mathit {1-{\frac {1}{2^{k}}}}})$-aproksymacyjny dla takiego problemu.

Wskazówka

Jak wygląda oszacowanie $P(r,f_{i})$, gdy $f_{i}$ reprezentuje klauzulę?

Rozwiązanie

Wystarczy zauważyć, że jeżeli $f_{i}$ reprezentuje klauzulę z $j$ literałami, to $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$k$FSAT i podany tam algorytm w tym wypadku jest algorytmem $({\mathit {1-{\frac {1}{2^{k}}}}})$-aproksymacyjnym.

Problemy $\mathrm {MAXSNP}$-zupełne

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

Twierdzenie 8.1

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

Dowód

Przypomnijmy, że klasa $\mathrm {MAXSNP}$ jest definiowana jako klasa problemów L-redukowalnych do problemów z $\mathrm {MAXSNP} _{0}$. Zatem wystarczy, że pokażemy, iż każdy problem z $\mathrm {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 $\mathrm {MAXSNP} _{0}$ definiowany formułą:

$\max _{S}\{{({\mathit {x_{1},x_{2},\ldots ,x_{k}}})}:{\phi }\}{\text{.}}$

Rozważymy teraz konkretną instancję problemu $A$ z ustalonym uniwersum $V$ i relacjami $G_{1},G_{2},\ldots ,G_{m}$. Dla każdej krotki $v=({\mathit {v_{1},v_{2},\ldots ,v_{k}}})\in V^{k}$ definiujemy formułę $\phi _{v}$, która powstaje z $\phi$ przez podstawienie wartości $v_{1},v_{2},\ldots ,v_{k}$ za zmienne $x_{1},x_{2},\ldots ,x_{k}$. Każdą w formuł $\phi _{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łę $\phi _{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}},\ldots ,v_{i_{r}})$, tak aby zmaksymalizować liczbę spełnionych formuł $\phi _{v}$. Jeżeli któraś z formuł $\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 $A$ do problemu MAX$l$FSAT, gdzie jest $|{\mathit {V}}|^{r}$ zmiennych odpowiadających $S(v_{i_{1}},v_{i_{2}},\ldots ,v_{i_{r}})$ i $|{\mathit {V}}|^{r}$ funkcji logicznych odpowiadających formułom $\phi _{v}$. Stała $l$ zależy tylko od postaci formuły $\phi$ i należy ją ustalić równą liczbie wystąpień symbolu relacyjnego $S$ w formule $\phi$. 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 $\phi _{v}$ jest reprezentowana przez co najwyżej $c$ klauzul, gdzie $c$ zależy tylko od liczby bramek potrzebnych do wyrażenia formuły $\phi$.

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}}({\text{opt}}(x)\geq dm$, ${\text{opt}}(R(x))\leq cm$) i $\beta =1$ (w rozwiązaniu optymalnym ${\text{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 8.2

Problemy z $\mathrm {MAXSNP} _{0}$ są aproksymowalne ze stałą.

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

Wskazówka

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

Rozwiązanie

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