NARZĘDZIA ALGORYTMIKI
wykład monograficzny jesień 2013
prowadzą Ł. Kowalik i M. Mucha
Zadania domowe: [seria I] [seria II]
Wykład 1: skojarzenia
Skojarzenia w grafach dwudzielnych - przypomnienie
- ścieżki powiększające,
- algorytm w czasie O(nm),
- twierdzenie Koniga-Egervary’ego
Skojarzenia w grafach dowolnych
- algorytm Edmondsa i jego implementacja w czasie O(n3)
- twierdzenie Berge-Tutte, tw. Tutte jako wniosek.
- twierdzenie Petersena jako wniosek z tw. Tutte.
Materiały:
Wykład 2: wstęp do matroidów
- motywacja: algorytm zachłanny dla MST i najcięższej bazy przestrzeni liniowej.
- definicja matroidu (przez własność uniformity)
- matroid grafowy, liniowy, jednorodny, suma prosta matroidów, matroid podziałowy
- własność augmentation (równoważna definicja)
- matroid skojarzeniowy, pokryciowy (transversal)
- baza, cykl, rząd
- twierdzenie o równoważności własności (weak augmentation, augmentation, uniformity, base exchange, circuit elimination, induced circuits, greedy algorithm, submodularity)
- algorytm zachłanny dla problemu szeregowania zadań
Materiały:
Wykład przygotowywałem na podstawie podręczników West “Graph Theory” oraz Lee “A first course in combinatorial optimization”. Pewną pomocą mogą być:
Wykład 3: przecięcie matroidów
- problemy najliczniejszego i najcięższego wspólnego zbioru niezależnego
- przykładowe zastosowania: skojarzenia w grafach dwudzielnych, minimum cost r-arborescence, orientacja z ograniczeniami stopni wychodzących
- twiedzenie Edmondsa o przecięciu matroidów, dowód algorytmiczny
- zastosowanie: kolorowe drzewa rozpinające
- twierdzenie o sumie matroidów (bez dowodu)
- zastosowanie: Matroid Covering Theorem, twierdzenie Nasha-Williamsa o lesistości
Materiały:
Wykład przygotowywałem w dużej mierze na podstawie książki A. Frank “Connections in combinatorial optimization”. Pewną pomocą mogą być
Wykład 4: algorytm elipsoid (Khachiyana)
- opis i analiza algorytmu
- wyrocznie oddzielające
- zastosowanie: LP dla MST
- zastosowanie: configuration LP dla problemu pakowania pudełek
Materiały:
W dalszym ciągu pierwszej z książek będę się odwoływał jako [SW], a do drugiej [LRS]. Jeśli ktoś nie lubi czytać wszystkiego co się rusza, to sugeruje przeczytać o MST w [LRS], a o pakowaniu w [SW].
Wykład 5: metoda prymalno-dualna
- Algorytm dla problemu pokrycia zbiorami
- Teoria: słabe tw. o dualności, komplementarne warunki swobody (dokładne i przybliżone)
- Algorytm dla problemu s-t-ścieżki
- Algorytm dla problemu lasu Steinera
Najlepszym źródłem jest rozdział 7 [SW], w którym jest wszystko co było na wykładzie i więcej. Dobry jest też rozdział 15 (pokrycie zbiorami) i 22 (las Steinera) w Vaziranim. Jeśli ktoś chciałby zobaczyć jak zawodowcy aproksymują problem drzewa Steinera, to można to znaleźć rozdziale 13.6 [LRS] (o tym tylko wspomniałem na wykładzie, dla osób o mocnych nerwach).
Wykład 6: programowanie półokreślone
- Programownie póokreślone na przykładzie problemu MAX-CUT:
- programy ściśle kwadratowe, wektorowe i półokreślone
- rozwiązywanie programów wektorowych i półokreślonych za pomocą metody elipsoid (i mała powtórka z algebry liniowej)
- zaokrąglanie rozwiązania, tu m.in. jak losować punkt na sferze
- Inne zastosowanie: aproksymacja problemu MAX-2SAT
O tym można przeczytać w wielu miejscach. Wykład był przygotowany na podstawie początku rozdziału 6 w [SW]. Rozdział 26 w Vaziranim też jest godny polecenia (w szczególności [SW] zawiera opis algorytmu dla MAX-2SAT tylko jako ćwiczenia, a w Vaziranim faktycznie jest to omówione).
Wykład 7 i pół 8-go: trudność aproksymacji
- Trudność (3/2-ε)-aproksymacji BIN-PACKING, pojęcie “luki”
- Klasa problemów PCPc,s(r(n),q(n)), twierdzenie PCP
- Trudność (½+ε)-aproksymacji problemu spełnialności więzów parzystości/nieparzystości (odd/even CSP)
- Trudność (7/8+ε)-aproksymacji problemu MAX-E3-SAT, redukcja zachowująca lukę
- Trudność c-aproksymacji problemu zbioru niezależnego, dla dowolnej stałej c<1
- Informacja o Unique Games Conjecture
- Trudność (23/24+ε)-aproksymacji problemu Label Cover
- Trundość (logn/24)-aproksymacji Set Cover (o ile problemy NP nie mają algorytmów Monte-Carlo w czasie O(n^loglogn))
Materiały: znakomitym tekstem źrodłowym (na podstawie którego przygotowywałem wykład) jest podręcznik Williamson-Shmoys.
Wykład kolejny: iterowane zaokrąglanie
- Iterowane zaokrąglanie na przykładzie szeregowania maszyn i drzew o ograniczonym stopniu wierzchołków.
Materiały: Zdecydowanie najlepszym źródłem jest książka http://www.cse.cuhk.edu.hk/~chi/papers/iterative.pdf, rozdziały 3.2 i 4. Można te przeczytać notatki 4 i 5 tutaj http://duch.mimuw.edu.pl/~mucha/wordpress/?page_id=303
Wykład 27.11 Zastosowania algorytmiczne nierówności Chernoffa
- Rzuty monetą
- Szacowanie ogonów w Quicksorcie z wyborem elementu dzielącego
- Routing na hiperkostce: algorytm uzgadniania bitów, algorytm dwufazowy
Materiały: Hiperkostka - książka Mitzenmacher, Upfal zawiera naszym zdaniem trochę błędną analizę. To co robiłem na wykładzie to mieszanka Mitzenmachera-Upfala (do momentu, w którym jest OK) i podejścia z tych notatek (których właściwie nie czytałem, ale wyglądają ok...).
Kolejny wykład
- Zaokrąglanie zależne na przykładzie problemu całkowitoliczbowego przepływu wielotowarowego o minimalnej przepustowości.
Materiały: Notatki 5 i 6 tutaj http://duch.mimuw.edu.pl/~mucha/wordpress/?page_id=303 . Zainteresowani mogą też zajrzeć do oryginalnej pracy Srinivasana et al. http://www.cs.umd.edu/~samir/grant/jacm06.pdf .
I następny
- Drzewa HST - konstrukcja i proste zastosowanie. O tym można poczytać w książce Shmoys-Williamson 8.5-8.6 lub w notatkach na tej stronie (wykład 7)
http://duch.mimuw.edu.pl/~mucha/wordpress/?page_id=303
Problem Group Steiner Tree, który jest omawiany w tych notatkach, nie był omawiany na zajęciach, ale algorytm jest fajny, polecam.
Wykłady o algorytmach on-line
Wykłady 15.12 i 22.12
- Rozmieszczenia kul w urnach.
- Dla n kul i urn z dużym prawdop. najbardziej zapełniona urna ma Theta(logn/loglogn) kul. (trudniejsze jest dolne ograniczenie: używamy aproksymacji przez zmienne Poissona)
- Siła podwójnego wyboru. Udowodniliśmy że przy m urnach i m/8 kulach każda urna ma O(loglogn) kul z d.p.
- rodziny k-uniwersalne i k-niezależne - definicja
- haszowanie przez łańcuchowanie
- rodzina funkcji liniowych (dowód 2-uniwersalności)
- rodzina tabulacyjna (dowód 3-niezależności i że nie jest 4-niezależna)
- haszowanie doskonałe
- haszowanie kukułkowe
- haszowanie liniowe
Materiały:
Klasyczny schemat urnowy wykładany był wg książki Mitzenmacher-Upfal “Metody Probabilistyczne i obliczenia” (punkty 5.2.1 i 5.4). Siła podwójnego wyboru -- wg tych notatek [ps]. Haszowanie wg moich wykładów na smurfie: [pierwszy] [drugi] [trzeci]