Introduction to approximation and randomized algorithms

NDMI084 Introduction to approximation and randomized algorithms

Winter semester 2023/24

Petr Kolman, Jiří Sgall

The weekly lecture takes place every Tuesday in Lecture room S5 (Mala Strana) from 3:40 - 5:10 pm. The tutorials take place once in two weeks on Wednesday from 9:00 - 10:30 am, and are led by Matej Lieskovský.

Lectures in the first half of the semester are given by Petr Kolman, and in the second half of the semester 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

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].

Starting from November 14 till, the end of the semester, the course is taught by Jiří Sgall.

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.

[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.

[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.

[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

Approximation Algorithms by Chandra Chekuri
Approximation Algorithms and Approximability by Mohammad R. Salavatipour
Approximation Algorithms by Anupam Gupta and R. Ravi