Autor: Vijay V. Vazarini

ISBN: 83-204-2977-3

Ilośc stron: 384

Data wydania: 11/2004

Twarda oprawa

Książka ALGORYTMY APROKSYMACYJNE 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.

Rozdziały:

Rozdział 1. 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. ℓ1-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