NDMI084 - Introduction to approximation and
randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů
Petr Kolman, Jiří Sgall
Fall 2023 - Tuesday 15:40 (3:40pm) in S5 (Malá
Strana)
Exercises (recitations) take place once in two weeks
on Wednesday from 9:00am, and are led by Matej Lieskovský.
The first half of the course (up to and including November 7)
was given by Petr
Kolman.
Czech lecture notes - poznámky k
přednášce
Covered topics
- October 3, 2023
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems.
- Approximation ratio [WS 1.1, V1].
- TSP - limits on approximation in the general setting.
- October 10
- Metric TSP - 2-approximation
- Christofides' 1.5-approximation [WS 2.4, V 3.2].
- Discrete probability - review of elementary definitions
and properties (see
old notes or more detailed Notes
on probability by J. Matousek).
- October 17
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- Contention resolution in a distributed system - randomized
protocol [KT 13.1].
- Randomized global minimum cut algorithm - intro [KT 13.2].
- October 24
- Randomized global minimum cut algorithm [KT 13.2].
- Scheduling on identical machines - local search [WS 2.3].
- October 31
- 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].
- November 7
- Greedy algorithm for edge disjoint paths in graphs [KT
11.5].
- Greedy algorithm for paths in graphs with capacities [KT
11.5].
- November 14
- Algorithms for MAX SAT [WS 5.1-5.5, V 16].
- Simple 1/2-approximation (RAND SAT).
- Approximation based on linear programming relaxation
and randomized rounding.
- Approximation of MAX SAT based on LP relaxation -
analysis.
- Choosing the better of two solutions - 3/4
approximation for MAX SAT [WS 5.5].
- November 21
- Algorithms for MAX SAT [WS 5.1-5.5, V 16].
- Biased randomized approximation algorithm. (Only in
tutorials.)
- Derandomization 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].
- Intuitive explanation of duality
- The greedy algorithm and its analysis using dual linear
program
- November 28
- 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
- December 5
- Parallel randomized algorithm for maximum independent set
problem - analysis [MR 12.3, the notes by E. Vigoda].
- Derandomization of the parallel alg. for max IS using
pairwise independent variables.
- December 12
- Hashing
- The dictionary problem and universal hashing [MR 8.4,
MU 13.3].
- 2-universal hashing and dynamic dictionary with
expected constant time per operation.
- Perfect hashing and static dictionary with constant
time per lookup in the worst case.
- December 19
- Randomized testing of matrix multiplication in linear time
[MR 7.1, MU 1.3]
- Randomized testing of polynomial identities [MR 7.1, MU
1.3].
- Testing the existence of perfect matchings in bipartite
and general graphs [MR 7.3].
- January 9, 2024
- Testing the existence of perfect matchings in bipartite and
general graphs [MR 12.4].
- Isolating lemma [MR 12.4].
- Parallel randomized algorithm for a perfect matching [MR
12.4].
Textbooks and Study Material
Notes and recordings from edition of the course in 2020/21
by Petr Kolman.
[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.