Algorytmy Aproksymacyjne 2007

Egzamin poprawkowy: wtorek, 11.03.2008, pokój 4310 a może 4180

Literatura

• [Vazirani] Vijay Vazirani "Algorytmy Aproksymacyjne"
• Oryginalne artykuły

Wykłady

1. (1.10 - 15.10) NP-trudne problemy optymalizacyjne. Algorytm aproksymacyjny (problemu minimalizacji) jako efektywna konstrukcja dolnego ograniczenia na rozwiązanie optymalne. Kombinatoryczne algorytmy aproksymacyjne:
   • 2-aproksymacja pokrycia wierzchołkowego,
   • H_n-aproksymacja pokrycia zbioru,
   • 2-aproksymacja drzewa Steinera,
   • nieaproksymowalność TSP,
   • 3/2-aproksymacja metrycznego TSP,
   • logn-aproksymacja metrycznego ATSP,
   • 1/2-aproksymacja max ATSP,
   • 2/3-aproksymacja max TSP,
   • proste algorytmy dla problemu najkrótszego nadsłowa,
   • schematy aproksymacji (problem plecakowy, bin-packing, ...)
   Materiały:
   • [Vazirani]
   • Skrytpt Marcina o problemie najkrótszego nadsłowa [PDF]
2. (22.10 - 29.10) Wstęp do programowania liniowego:
   • postać kanoniczna, standardowa i dopełnieniowa,
   • geometria PL (równoważność wierchołka, rozwiązania ekstremalnego i bazowego rozwiązania dopuszczalnego),
   • lemat Farkasa, słaba dualność, silna dualność, komplementarne warunki swobody,
   • informacja o algorytmach wielomianowych,
   • twierdzenie o maksymalnym przepływie i minimalnym przekroju jako wniosek dualności PL.
   Materiały:
   • moje notatki [PDF]
   • Notatki do wykładu "Advanced Algorithms" E. Demiane'a i D. Karger'a (2003)
   • Notatki do wykładu "Advanced Algorithms" M. Goemans'a (1994) [PS]
   • [Vazirani]
3. (22.10 - 12.11) Zastosowanie PL do algorytmów aproksymacyjnych:
   • programy całkowitoliczbowe,
   • pojęcie relaksacji, luka całkowitości,
   • zaokrąglanie (f-aproksymacja pokrycia zbioru),
   • dowód że algorytm zachłanny dla pokrycia zbioru jest H_n-aproksymacyjny przez konstrukcję rozwiązania dopuszczalnego PL,
   • luka całkowitości pokrycia wierzchołkowego (2),
   • luka całkowitości pokrycia zbioru (\Theta(\logn)),
   • algorytm 3/4-aproksymacyjny dla problemu MAX-SAT (Rozdział 16) w tym derandomizacja metodą warunkowej wartości oczekiwanej,
   • algorytm 2-aproksymacyjny dla problemu szeregowania zadań na niezależnych maszynach (Rozdział 17).
   • schemat prymalno-dualny dla problemu pokrycia zbioru (Rozdział 15),
   • schemat prymalno-dualny dla problemu lasu Steinera (Rozdział 22).
   Materiały: [Vazirani]
4. (19.11) Programowanie półokreślone i wektorowe -- zastosowania do aproksymacji
   • 0.878-aproksymacja MAX-CUT,
   • 0.878-aproksymacja MAX-2-SAT,
   • n^{1/4}*logn-aproksymacja kolorowania grafów 3-kolorowalnych.
   Materiały: [Vazirani,...]
5. (26.11) Problem komiwojażera, część I.
   • Algorytm 3/4-aproksymacyjny dla maxTSP (Serdyukov),
   • Algorytm 3/4-aproksymacyjny dla asymetrycznego maxTSP z nierównością trójkąta (Kostochka-Serdyukov),
   • Program liniowy eliminacji podtras i jego związki z programami liniowymi dla MST i doskonałego skojarzenia. Ograniczenie luki relaksacji do 4/3 (dolna granica) i 3/2 (górna)
   Materiały:
   • Hassin, Rubinstein "Better Approximations for Max TSP" (IPL 1998) [CiteSeer], str. 2.
   • Kaplan, Lewenstein, Shafrir, Sviridenko, "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs" (JACM 2005) [PDF], strony 17-18.
   • Zadanie 23.13 z Vaziraniego
6. (03.12) Problem komiwojażera, część II: warianty asymetryczne
   • Twierdzenie o parze pokryc cyklowych bez wspolnego 2-cyklu,
   • Algorytm 0.787*log_2n-aproksymacyjny dla asymetrycznego min TSP z nierównością trójkąta,
   • Algorytm 2/3-aproksymacyjny dla asymetrycznego max TSP,
   • Algorytm 10/13-aproksymacyjny dla asymetrycznego maxTSP z nierównością trójkąta.
   Materiały:
   • Kaplan, Lewenstein, Shafrir, Sviridenko, "Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs" (JACM 2005) [PDF],
   • Uriel Feige, Mohit Singh, "Improved approximation ratios for traveling salesperson tours and paths in directed graphs" (nieopubl., 2006) [PDF]
     (W tej pracy pojawia się inny opis algorytmu dla minTSP, z troche poprawioną analizą -- tą wersję opowiadałem na wykładzie. Jest tam też odrobinkę lepszy algorytm, 2/3*log_2n-aproksymacyjny, ale o nim nie opowiadałem.)
7. (03.12) Problem komiwojażera, część III: lepsze algorytmy dla metrycznego maxTSP
   • Algorytm 11/14-aproksymacyjny dla asymetrycznego max TSP z nierównością trójkąta,
   • Algorytm 35/44-aproksymacyjny dla asymetrycznego max TSP z nierównością trójkąta (szkic),
   • Algorytm 7/8-O(1/sqrt{n})-aproksymacyjny dla max TSP z nierównością trójkąta (bardzo mglisty szkic).
   Materiały:
   • Kowalik, Mucha, " 35/44-Approximation for Asymmetric Maximum TSP with Triangle Inequality" (WADS 2007) [PDF],
   • Hassin, Rubinstein, "A 7/8-approximation algorithm for metric Max-TSP" (IPL 2002) [PDF]
8. (10.12-7.01) Problem najkrótszego nadsłowa (Shortest Superstring)
   • Overlap graph, prefix graph
   • Redukcja do instancji o małym overlapie -- jak i po co?
   • Zastosowanie c-aproksymacji maxTSP do (4-2c)-aproksymacji najkrótszego nadsłowa
   • Zastosowanie c-aproksymacji maxTSP do (3.5-1.5c)-aproksymacji najkrótszego nadsłowa
   • Algorytm zachłanny: dolne ograniczenie na wsp. aproksymacji, znajdowanie pokrycia cyklowego przez algorytm zachłanny, algorytm cycle-greedy i jego współczynnik aproksymacji.
   Materiały: Skrytpt Marcina o problemie najkrótszego nadsłowa [PDF]
9. (7.01-14.01) Zliczanie przybliżone i jego zastosowania
   • Klasa #P i problemy #P-zupełne,
   • Pojęcie w pełni wielomianowego randomizowanego schematu aproksymacji dla problemów zliczania (FPRAS),
   • FPRAS dla problemu zliczania formuł w postaci DNF,
   • Problem niezawodności sieci.
   Materiały: [Vazirani] -- rozdział 28.
10. (21.01) Trudność aproksymacji
    • Klasa APX i problemy APX-trudne,
    • Trudność problemów TSP i BIN PACKING,
    • Redukcja wprowadzająca / zachowująca lukę
    • Klasa problemów PCP_{a,b}(r(n),q(n))
    • Sformułowanie twierdzenia PCP
    • Równoważność APX-trudności problemu MAX-3-SAT i twierdzenia PCP,
    Materiały: [Vazirani] -- rozdział 29.

---