NDMI084 - Introduction to approximation and
randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů
Petr Kolman, Jiří Sgall
Fall 2016 - Tuesday 14:00 in S4
Česká
cvičení se konají jednou za 14 dnů v pondělí
od 14:00,
vede je Martin Böhm.
English
classes (recitations)
take place once in two weeks on Monday at 2 pm and are led
by
Martin Böhm.
The first half of the course was given by Petr Kolman
Předchozí běh přednášky v r. 2015
[previous
year]
Covered topics
- October 4
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems, approximation
algorithm and ratio [WS 1.1, V1].
- TSP - limits on approximation in the general setting,
2-approximation for the metric TSP [WS 2.4].
- October 11
- 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).
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- October 18
- Contention resolution in a distributed system - randomized
protocol [KT 13.1].
- Randomized minimum cut algorithm [KT 13.2].
- October 25
- Scheduling on identical machines - local search, greedy
(list
scheduling, longest processing time first), online [WS 2.3].
- November 1
- Greedy algorithms for bin packing (first fit, best fit, any
fit, online) [WS 3.3, V 9].
- Greedy algorithm for edge disjoint paths in graphs [KT
11.5].
- Greedy algorithm for paths in graphs with capacities [KT
11.5].
- November 8 - no lectures, Dean's Sports Day
- November 15
- Greedy algorithm for paths in graphs with capacities -
contd.
[KT 11.5].
- 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
- November 22
- MAX SAT approximation based on linear programming
relaxation,
contd. [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]
- November 29
- algorithms for vertex and set cover [WS 1.2-1.6, 7.1, V
13-14]
- rounding of the linear program solution
- primal-dual algorithm
- the greedy algorithm and its analysis using dual linear
program
- December 6
- December 13
- fast parallel randomized algorithm for maximal independent
set in graphs (continued)
- derandomization using pairwise independent variables
- universal systems of hash functions and their use [MR 8.4,
MU 13.3]
- December 20
- 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]
- 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]
- January 3
- a fast parallel randomized algorithm for perfect matching in
bipartite and general graphs [MR 7.3, 12.4]
- January 10
- a fast parallel randomized algorithm for perfect matching in
bipartite and general graphs [MR 7.3, 12.4]
- 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.