Úvod do aproximačních a pravděpodobnostních algoritmů NDMI084

Zimní semestr 2017/18

Petr Kolman, Jiří Sgall

Přednášky (P. Kolman): pondělí 9:00 - 10:30 v S9.

Lectures in English (J. Sgall): Monday 14:00 - 15:30 in S5.

Česká cvičení: jednou za 14 dnů v uterý od 17:20, vede je Pavel Veselý.

English classes (recitations): once in two weeks on Monday at 3:40 pm and are led by Pavel Veselý.

Lecture notes by J. Sgall (in Czech)

Probraná látka

• 2.10.2017
  • Úvod.
  • Pravděpodobnostní protokol pro výpočet průměrného platu.
  • Optimalizační a NP optimalizační problémy, aproximační algoritmy, aproximační poměr [WS 1.1, V1].
  • Problém obchodního cestujícího (TSP)- hranice možnosti aproximovat.
• 9.10.2017
  • Kostrový 2-aproximační algoritmus pro metrický TSP [WS 2.4].
  • Christofidesuv 1.5-aproximační algoritmus pro metrický TSP (kostra + párování) [WS 2.4, V 3.2].
  • Diskrétní pravděpodobnostní prostor - opakování základních pojmů a vlastností (viz např. Úvod do diskrétní pravděpodobnosti prof. J. Matouška).
  • Quicksort [MU 2.5, MR 1, KT 13.5].
• 16.10.2017 (prof. J. Sgall)
  • Konflikty v distribuovaném systému [KT 13.1].
  • Minimální řez v grafu [KT 13.2].
• 23.10.2017
  • Rozvrhování na indentických strojích - lokální prohledávání, hlad. alg. [WS 2.3].
  • Online algoritmy a rozvrhování.
• 30.10.2017
  • Plnění popelnic (First Fit, Best Fit, Any Fit) [WS 3.3].
  • Hledání disjuktních cest v grafu [KT 11.5].
  • Hledání skoro disjuktních cest v grafu s kapacitami [KT 11.5].
• 6.11.2017
  • MAX SAT, jednoduché pravděpodobnostní algoritmy (Rand SAT, Biased SAT) [WS 5.1,5.3].
  • Pravděpodobností zaokrouhlování (Randomized Rounding) pro MAX SAT [WS 5.4].
• 13.11.2017
  • MAX SAT - algoritmus Best SAT [WS 5.5].
  • MAX SAT - derandomizace algoritmu Rand SAT [WS 5.4].
  • Množinové pokrytí (Set cover) - hladový algoritmus (jen popis), LP relaxace a jednoduché zaokrouhlování [WS 1.2-1.6, 7.1, V 13-14].
• 20.11.2017
  • Množinové pokrytí - duální a primálně duální algoritmus, analýza hladového algoritmu [WS 1.2-1.6, 7.1, V 13-14].
  • Maximální nezávislá množina - paralelní algoritmus (jen popis) [MR 12, viz též Lecture notes Erica Vigody].
• 27.11.2017
  • Maximální nezávislá množina - paralelní algoritmus, analýza [MR 12, viz též Lecture notes Erica Vigody].
• 4.12.2017
  • MIS - paralelní algoritmus, nástin derandomizace pomocí po dvou nezávislých náhodných proměnných [MR 12, viz též Lecture notes Erica Vigody].
  • Hašování - úvod. 2-univerzální množiny hašovacích funkcí. [MU 13.3]
• 11.12.2017
  • Dynamický slovník pomocí hašování s konstatní střední hodnotou času na operaci. [MR 8.4, MU 13.3.3]
  • Statický slovník pomocí hašování s konstatním časem na operaci - perfektní hašování. [MR 8.5, MU 13.3.3]
• 18.12.2017
  • Pravděpodobnostní testování identit polynomů. [MR 7.2, MU 1.1]
  • Pravděpodobnostní testování existence perfetního párování v bipartitním grafu. [MR 7.3]
  • Pravděpodobnostní testování existence perfetního párování v obecném grafu. [MR 7.3, 12.4]
• 8.1.2018
  • Paralelní pravděpodobnostní algoritmus na hledání perfetního párování v obecném grafu. [MR 12.4]

Sylabus

Přednáška probírá středně pokročilé techniky pro návrh a analýzu algoritmů a ilustruje je na konkrétních kombinatorických problémech. Pro mnohé optimalizační problémy je obtížné navrhonout algoritmy, které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Často pro návrh algoritmů (aproximačních i jiných) používáme náhodnost, což umožňuje řešit některé úlohy efektivněji nebo řešit úlohy jinak neřešitelné. Doporučeno pro 3. ročník bakalářského studia.

Probírané techniky:

• Hladový algoritmus jako metoda pro návrh aproximačních a online algoritmů
• Použití lineárního programování pro návrh aproximačních algoritmů
• Po dvou nezávislé náhodné proměnné
• Odstranění náhodnosti metodou podmíněných pravděpodobností
• Lokální prohledávání

Probírané problémy a algoritmy:

• Rozvrhování a hledání disjunktních cest v grafu - hladové algoritmy
• Problém obchodního cestujícího a vrcholové pokrytí - jednoduché kombinatorické aproximační algoritmy
• Množinové pokrytí - hladový algoritmus, použití lineárního programování
• Splnitelnost (MAX-SAT) - použití lineárního programování, náhodné zaokrouhlování, derandomizace
• Hashování dynamické a statické - pravděpodobnostní algoritmy, po dvou nezávislé náhodné proměnné
• Největší řez v grafu - aproximace pomocí lokálního prohledávání
• Maximální nezávislá množina v grafu - rychlý pravděpodobnostní paralelní algoritmus
• Verifikace maticových rovnic - pravděpodobnostní protokol

Učebnice

There is no required textbook but the material presented in the course is covered by several good books.

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.

[MR] R. Motwani, P. Raghavan: Randomized algorithms, Cambridge University Press, 1995.

[MU] M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, 2005.

[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.

[KT] J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.

Other courses on approximation or randomized algorithms

• Approximation Algorithms by Chandra Chekuri
• Approximation Algorithms and Approximability by Mohammad R. Salavatipour
• Approximation Algorithms by Anupam Gupta and R. Ravi