NDMI084 - Introduction to approximation and
randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů
Petr Kolman, Jiří Sgall
Fall 2017 - Monday 14:00 in S5
English section
English
exercises (recitations) take place once in
two weeks on Monday at 15:40 in S7 and are led by Pavel
Veselý
Czech section
Česká
přednáška se koná v pondělí od 9:00 v S9, přednáší
Petr Kolman
Česká
cvičení se konají jednou za 14 dnů v úterý od
17:20, vede je Pavel Veselý
Covered topics
- October 2
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems, approximation
algorithm and ratio [WS 1.1, V1].
- October 9
- TSP - limits on approximation in the general setting,
2-approximation for the metric TSP [WS 2.4].
- Metric TSP - Christofides 1.5-approximation [WS 2.4, V 3.2].
- Discrete probability - review of elementary definitions and
properties (see Notes
on probability by J. Matousek).
- October 16
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- Contention resolution in a distributed system - randomized
protocol [KT 13.1].
- Randomized minimum cut algorithm [KT 13.2].
- October 23
- Scheduling on identical machines - local search, greedy
(list scheduling, longest processing time first) [WS 2.3].
- Greedy algorithms for bin packing (first fit, best fit, any
fit) [WS 3.3, V 9].
- October 30
- Online algorithms - scheduling on identical machines, bin
packing [WS 2.3, WS 3.3].
- Greedy algorithm for edge disjoint paths in graphs [KT
11.5].
- Greedy algorithm for paths in graphs with capacities [KT
11.5].
- November 6
- Randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
- simple 1/2-approximation algorithm for MAX SAT (RAND SAT
ALG), 7/8-approximation algorithm for MAX-E3-SAT
- biased randomized approximation algorithm
- approximation based on linear programming relaxation
(randomized rounding) [WS 5.4]
- November 13
- Randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
- continued
- Choosing the better of two solutions - 3/4 approximation
for MAX SAT [WS 5.5]
- Derandomization of RAND SAT ALG by the method of
conditional expectation [WS 5.3]
- algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V
13-14]
- rounding of the linear program solution
- the greedy algorithm and its analysis using dual linear
program
- November 20
- algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V
13-14] - continued
- November 27
- December 4
- universal systems of hash functions and their use [MR 8.4,
MU 13.3]
- dynamic dictionary with expected constant time per operation
[MR 8.4, MU 13.3.3]
- static dictionary with expected constant time per lookup in
the worst case [MR 8.5, MU 13.3.3]
- December 11
- randomized testing of matrix multiplication in linear time
[MR 7.1, MU 1.3]
- randomized testing of polynomial identities [MR 7.2, MU 1.1]
- a fast parallel randomized algorithm for perfect matching in
bipartite and general graphs [MR 7.3, 12.4]
- December 18
- a fast parallel randomized algorithm for perfect matching in
bipartite and general graphs [MR 7.3, 12.4]
- January 8
- 2-approximation algorithm for scheduling on unrelated
machines [V 17, WS 11.1]
Syllabus
This course covers techniques for design and analysis of
algorithms, demonstrated on concrete combinatorial problems. For
many optimization problems it is impossible (or NP-hard) to design
algorithms that finds an optimal solution fast. In such a case we
study approximation algorithms that work faster, at the cost that
we find a good solution, not necessarily an optimal one. Often we
use randomness in design of (approximation and other) algorithms,
which allows to solve problems more efficiently or even to solve
problems that are otherwise intractable. Recommended for the 3rd
year.
Sylabus [Detailed syllabus in Czech]
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
Textbooks:
[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.