NDMI084 - Introduction to approximation and
randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů
Petr Kolman, Jiří Sgall
Fall 2019 - Monday 10:40 v S3
Česká cvičení se konají jednou za 14 dnů ve středu
od 15:40, vede je Michal Berg.
English exercises (recitations) take place once in two
weeks on Wednesday at 3:40 pm and are led by Michal Berg.
The first half of the course will be given by Petr Kolman
Czech lecture notes - poznámky k
přednášce (verze 8. 1. 2020)
Covered topics
- (1 -PK) October 7
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems.
- Approximation ratio [WS 1.1, V1].
- (2 -PK) October 14
- TSP - limits on approximation in the general setting.
- Metric TSP - 2-approximation, 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).
- (3 -PK) October 21
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- Contention resolution in a distributed system - randomized
protocol [KT 13.1].
- (4 - PK) November 4
- Randomized global minimum cut algorithm [KT 13.2].
- Scheduling on identical machines - local search [WS 2.3].
- (5 - PK) November 11
- Greedy algorithm for scheduling on identical machines
(list scheduling, longest processing time first), online [WS
2.3].
- Greedy algorithms for bin packing (first fit, best fit,
any fit) [WS 3.3, V 9].
- Greedy algorithm for edge disjoint paths in graphs [KT
11.5].
- (6 - PK) November 18
- Greedy algorithm for edge disjoint paths in graphs -
analysis.
- Greedy algorithm for paths in graphs with capacities [KT
11.5].
- Randomized algorithms for satisfiability [WS 5.1-5.5, V
16].
- Simple 1/2-approximation algorithm (RAND SAT).
- Biased randomized approximation algorithm.
- (7 - JS) November 25
- Randomized algorithms for satisfiability [WS 5.1-5.5, V 16]
- continued
- approximation based on linear programming relaxation
(randomized rounding) [WS 5.4]
- 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]
- (8 - JS) December 2
- algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V
13-14]
- intuitive explanation of duality
- rounding of the linear program solution
- the greedy algorithm and its analysis using dual linear
program
- (9 - JS) December 9
- (10 - JS) December 16
- 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]
- (11 - JS) January 6
- a fast parallel randomized algorithm for perfect matching in
bipartite and general graphs [MR 7.3, 12.4]
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.
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