Introduction to approximation and randomized algorithms

NDMI084 Introduction to approximation and randomized algorithms

Winter semester 2019/20

Petr Kolman, Jirí Sgall

Lectures take place on Mondays at 10:40 - 12:10 pm, lecture room S3.

Česká svičení se konají jednou za 14 dnů ve středu od 15:40, vede je Michal Berg.

English tutorial take place once in two weeks on Wednesday at 3:40 pm and are led by Michal Berg.

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 7
- Introduction.
- Randomized protocol for computing the average salary.
- Optimization and NP-optimization problems.
- Approximation ratio [WS 1.1, V1].
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).
October 21
- Randomized Quicksort [MU 2.5, MR 1, KT 13.5].
- Contention resolution in a distributed system - randomized protocol [KT 13.1].
October 28
- National holiday - no lecture.
November 4
- Randomized global minimum cut algorithm [KT 13.2].
- Scheduling on identical machines - local search [WS 2.3].
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].
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.

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

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