Książka jest poświęcona algorytmom aproksymacyjnym, czyli algorytmom
jak najlepiej przybliżającym dokładne rozwiązanie zadań optymalizacyjnych.
Składa się z trzech części. Pierwsza dotyczy aproksymacyjnych algorytmów
kombinatorycznych dla wielu ważnych problemów, druga - zastosowania programowania
liniowego w projektowaniu algorytmów aproksymacyjnych, a trzecia - trudności związanych
z aproksymacjami i zliczaniem. Jest to doskonały podręcznik, o wielkich walorach
dydaktycznych, napisany z dużym znawstwem tematu. Każdy rozdział kończy się
ćwiczeniami do samodzielnego rozwiązania i rysem historycznym dotyczącym poruszanych w
rozdziale problemów, wzbogacającym wiedzę Czytelnika.
Książka jest przeznaczona dla studentów informatyki. Przyda się również
pracownikom naukowym i informatykom tworzącym nowoczesne oprogramowanie.
Spis treści:
Przedmowa
Rozdział l. Wstęp
1.1. Ograniczenie dolne OPT
1.1.1. Algorytm aproksymacyjny dla licznościowego problemu pokrycia wierzchołkowego
1.1.2. Czy można poprawić gwarancję aproksymacji?
1.2. Problemy dobrze określone i zależności minimaksowe
1.3. Zadania
1.4. Uwagi
Część I. Algorytmy kombinatoryczne
Rozdział 2. Pokrycie zbioru
2.1. Algorytm zachłanny
2.2. Rozwarstwianie
2.3. Zastosowanie problemu najkrótszego nadsłowa
2.4. Zadania
2.5. Uwagi
Rozdział 3. Drzewo Steinera i problem komiwojażera
3.1. Metryczny problem drzewa Steinera
3.1.1. Algorytm z wykorzystaniem minimalnego drzewa rozpinającego
3.2. Metryczny problem komiwojażera
3.2.1. Prosty algorytm o współczynniku 2
3.2.2. Poprawianie współczynnika aproksymacji do 3/2
3.3. Zadania
3.4. Uwagi
Rozdział 4. Przekrój wielokrotny i k-przekrój
4.1. Problem przekroju wielokrotnego
4.2. Problem minimalnego k-przekroju
4.3. Zadania
4.4. Uwagi
Rozdział 5. Problem k-centrum
5.1. Zastosowanie odcinania parametrycznego do metrycznego problemu
/.-centrum
5.2. Wersja ważona
5.3. Zadania
5.4. Uwagi
Rozdział 6. Rozcyklający zbiór wierzchołków
6.1. Cyklomatyczne funkcje -wagowe
6.2. Zastosowanie rozwarstwiania do problemu rozcyklającego zbioru
wierzchołków
6.3. Zadania
6.4. Uwagi
Rozdział 7. Najkrótsze nadsłowo
7.1. Algorytm 4-aproksymacyjny
7.2. Algorytm 3-aproksymacyjny
7.2.1. Algorytm osiągający połowę optymalnej kompresji
7.3. Zadania
7.4. Uwagi
Rozdział 8. Problem plecakowy
8.1. Algorytm pseudowielomianowy dla problemu plecakowego
8.2. Algorytm FPTAS dla problemu plecakowego
8.3. Silna NP-trudność a istnienie algorytmu FPTAS
8.3.1. Czy algorytm FPTAS jest najlepszym algorytmem proksymacyjnym?
8.4. Zadania
8.5. Uwagi
Rozdział 9. Pakowanie
9.1. Asymptotyczny schemat PTAS
9.2. Zadania
9.3. Uwagi
Rozdział 10. Najkrótsze uszeregowanie
10.1. Algorytm 2-aproksymacyjny
10.2. Algorytm PTAS dla problemu najkrótszego uszeregowan
10.2.1. Problem pakowania z ustaloną liczbą rozmiarów przedmiotów
10.2.2. Redukcja problemu najkrótszego szeregowania do ograniczonego problemu pakowania
10.3. Zadania
10.4. Uwagi
Rozdział 11. Euklidesowy problem komiwojażera
11.1. Algorytm
11.2. Dowód poprawności
11.3. Zadania
11.4. Uwagi
Część II. Algorytmy oparte na programowaniu liniowym
Rozdział 12. Wprowadzenie do dualności programowania liniowego
12.1. Twierdzenie o dualności PL
12.2. Zależności minimaksowe i dualność PL
12.3. Dwie podstawowe techniki
12.3.1. Porównanie technik oraz pojęcie luki całkowitości
12.4. Zadania
12.5. Uwagi
Rozdział 13. Dopasowanie dualne dla problemu pokrycia zbioru
13.1. Analiza algorytmu zachłannego dla problemu pokrycia, zbioru
wykonana metodą dopasowania dualnego
13.1.1. Czy można poprawić gwarancję aproksymacji?
13.2. Uogólnienia problemu pokrycia zbioru
13.2.1. Zastosowanie dopasowania dualnego do problemu ograniczonego multipokrycia zbioru
13.3. Zadania
13.4. Uwagi
Rozdział 14. Zastosowanie zaokrąglania do problemu pokrycia zbioru
14.1. Prosty algorytm zaokrąglania
14.2. Zaokrąglanie randomizowane
14.3. Półcałkowitoliczbowość problemu pokrycia wierzchołkowego
14.4. Zadania
14.5. Uwagi
Rozdział 15. Schemat prymalno-dualny dla problemu pokrycia zbioru
15.1. Ogólny opis schematu
15.2. Zastosowanie schematu prymalno-dualnego do problemu pokrycia zbioru
15.3. Zadania
15.4. Uwagi
Rozdział 16. Maksymalna spełnialność
16.1. Algorytm dla dużych klauzul
16.2. Derandomizacja metodą warunkowej wartości oczekiwanej
16.3. Algorytm zaokrąglania dla małych klauzul
16.4. Algorytm 3/4-aproksymacyjny
16.5. Zadania
16.6. Uwagi
Rozdział 17. Szeregowanie zadań na niezależnych maszynach
17.1. Odcinanie parametryczne w kontekście programowania liniowego
17.2. Własności rozwiązań ekstremalnych
17.3. Algorytm
17.4. Inne własności rozwiązań ekstremalnych
17.5. Zadania
17.6. Uwagi
Rozdział 18. Multiprzekrój i całkowitoliczbowy przepływ wielotowarowy w
drzewach
18.1. Problemy i ich relaksacje
18.2. Algorytm oparty na schemacie prymalno-dualnym
18.3. Zadania
18.4. Uwagi
Rozdział 19. Przekrój wielokrotny
19.1. Interesująca relaksacja PL
19.2. Randomizowany algorytm zaokrąglania
19.3. Półcałkowitoliczbowość problemu wierzchołkowego przekroju
wielokrotnego
19.4. Zadania
19.5. Uwagi
Rozdział 20. Multiprzekrój w dowolnych grafach
20.1. Sumaryczny przepływ wielotowarowy
20.2. Algorytm zaokrąglania
20.2.1. Wzrost obszaru: proces ciągły
20.2.2. Proces dyskretny
20.2.3. Algorytm znajdujący obszary
20.3. Trudny przypadek
20.4. Zastosowania problemu minimalnego multiprzekroju
20.5. Zadania
20.6. Uwagi
Rozdział 21. Najbardziej rozrzedzony przekrój
21.1. Wymagany przepływ wielotowarowy
21.2. Sformułowanie w postaci zadania PL
21.3. Metryki, upakowania przekrojów i ?1-zanurzalność
21.3.1. Upakowania przekrojów
21.3.2. l1-zanurzalność metryk
21.4. Mało zniekształcające ?1-zanurzenia metryk
21.4.1. Zagwarantowanie, by pojedyczna krawędź nie była za bardzo skracana
21.4.2. Zagwarantowanie, by żadna krawędź nie była za bardzo skracana
21.5. Algorytm zaokrąglania
21.6. Zastosowania
21.6.1. Ekspansywność krawędziowa
21.6.2. Przewodność
21.6.3. Przekrój zrównoważony
21.6.4. Uporządkowanie o minimalnych przekrojach
21.7. Zadania
21.8. Uwagi
Rozdział 22. Las Steinera
22.1. Relaksacja PL i zadanie dualne
22.2. Schemat prymalno-dualny z jednoczesnymi zmianami
22.3. Analiza
22.4. Zadania
22.5. Uwagi
Rozdział 23. Sieć Steinera
23.1. Relaksacja PL i półcałkowitoliczbowość
23.2. Technika zaokrąglania iterowanego
23.3. Charakteryzacja rozwiązań ekstremalnych
23.4. Dowód przez zliczanie
23.5. Zadania
23.6. Uwagi
Rozdział 24. Problem lokalizacji
24.1. Interpretacja zadania dualnego
24.2. Osłabianie prymalnych komplementarnych warunków swobody
24.3. Algorytm oparty na schemacie prymalno-dualnym
24.4. Analiza
24.4.1. Złożoność czasowa
24.4.2. Trudny przypadek
24.5. Zadania
24.6. Uwagi
Rozdział 25. Problem k-mediany
25.1. Relaksacja PL i zadanie dualne
25.2. Zarys algorytmu
25.3. Zaokrąglanie randomizowane
25.3.1. Derandomizacja
25.3.2. Złożoność czasowa
25.3.3. Trudny przypadek
25.3.4. Luka całkowitości
25.4. Zastosowanie relaksacji Lagrange'a w algorytmach aproksymacyjnych
25.5. Zadania
25.6. Uwagi
Rozdział 26. Programowanie półokreślone
26.1. Zadania ściśle kwadratowe i zadania wektorowe
26.2. Własności macierzy półokreślonych dodatnio
26.3. Problem programowania półokreślonego
26.4. Algorytm zaokrąglania randomizowanego
26.5. Poprawianie gwarancji aproksymacji dla problemu MAX-2SAT
26.6. Zadania
26.7. Uwagi
Część III. Inne zagadnienia
Rozdział 27. Najkrótszy wektor
27.1. Bazy, wyznaczniki i defekt ortogonalności
27.2. Algorytm Euklidesa i algorytm Gaussa
27.3. Ograniczenie dolne OPT za pomocą ortogonalizacji Grama-Schmidta
27.4. Rozszerzenie na n wymiarów
27.5. Krata dualna i jej zastosowanie algorytmiczne
27.6. Zadania
27.7. Uwagi
Rozdział 28. Zliczanie
28.1. Zliczanie rozwiązań DNF-formuły
28.2. Niezawodność sieci
28.2.1. Ograniczenie górne liczby przekrojów bliskich minimalnemu
28.2.2. Analiza
28.3. Zadania
28.4. Uwagi
Rozdział 29. Trudność aproksymacji
29.1. Redukcje, luki i współczynniki trudności
29.2. Twierdzenie PCP
29.3. Trudność problemu MAX-3SAT
29.4. Trudność problemu MAX-3SAT z ograniczoną liczbą wystąpień
zmiennych
29.5. Trudność problemów pokrycia wierzchołkowego i drzewa Steinera
29.6. Trudność problemu kliki
29.7. Trudność problemu pokrycia zbioru
29.7.1. Charakteryzacja NP ? jednorundowy system dowodów z dwoma rzecznikami
29.7.2. Gadżet
29.7.3. Zmniejszanie prawdopodobieństwa błędu poprzez wykonania równolegle
29.7.4. Redukcja
29.8. Zadania
29.9. Uwagi
Rozdział 30. Problemy otwarte
30.1. Problemy z rozwiązaniami o stałym współczynniku aproksymacji
30.2. Inne problemy optymalizacyjne
30.3. Problemy zliczania
30.4. Uwagi
Rozdział A. Przegląd teorii złożoności obliczeniowej
A.l. Świadectwa i klasa NP
A.2. Redukcje i NP-zupełność
A.3. Problemy NP-optymalizacyjne i algorytmy aproksymacyjne
A.3.l. Redukcje zachowujące współczynnik aproksymacji
A.4. Randomizowane klasy złożoności
A.5. Samoredukowalność
A.6. Uwagi
Rozdział B. Podstawowe fakty z teorii prawdopodobieństwa
B.l. Wartość oczekiwana i momenty
B.2. Odchylenia od wartości oczekiwanej
B.3. Podstawowe rozkłady prawdopodobieństwa
B.4. Uwagi
Literatura
Skorowidz problemowy
382 strony, B5, oprawa twarda
