NDMI084 Introduction to approximation and randomized algorithms

Winter semester 2022/23

Petr Kolman

The weekly lecture takes place every Wednesday in Lecture room S3 (Mala Strana) from 2 - 3:30 pm.

The tutorials take place once in two weeks on Tuesday from 2:00 - 3:30 pm and are led by Matej Lieskovský.

Czech Lectures take place on Monday at 12:20 - 13:50 pm, lecture room S3, and are given by Jiří Sgall.

Lecture notes by J. Sgall (in Czech)

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.

Covered topics

Study Material

Notes and recordings from edition of the course in 2020/21.

Textbooks

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.

For introduction to Linear Programming whose elementary knowledge is expected in this course, we recommend the first three chapters of the textbook Understanding and Using Linear Programming by J. Matousek and B. Gärtner (a preliminary Czech version is available as Lineární programování a lineární algebra pro informatiky).

Other courses on approximation or randomized algorithms