NDMI084 - Introduction to approximation and randomized algorithms
Úvod do aproximačních a pravděpodobnostních algoritmů

Petr Kolman, Jiří Sgall

Fall 2025 - Monday 12:20 in S4 (Malá Strana)

Exercises (recitations) take place once in two weeks on Monday, 2:00 - 3:30 pm, in S10, and are led by Cyril Kotecký.

The first half of the course (up to and including November 3) was given by Petr Kolman.

Czech lecture notes - poznámky k přednášce

Covered topics

• September 29, 2025
  • 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 6
  • 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. Matoušek).
• October 13
  • 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 20
  • Randomized global minimum cut algorithm [KT 13.2].
  • Greedy algorithms: Scheduling on identical machines - local search [WS 2.3].
• October 27
  • 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 - introduction [KT 11.5].
• November 3
  • Greedy algorithm for edge disjoint paths in graphs [KT 11.5].
  • Greedy algorithm for paths in graphs with capacities [KT 11.5].
  • Simple 1/2-approximation (RAND SAT) for MAX SAT.
• November 10
  • Algorithms for MAX SAT [WS 5.1-5.5, V 16].
    
    • Biased randomized approximation algorithm.
    • Approximation based on linear programming relaxation and randomized rounding.
    • Choosing the better of two solutions - 3/4 approximation for MAX SAT [WS 5.5].
    • Derandomization by the method of conditional expectation [WS 5.3].
• November 24
• 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
  • Rounding of the linear program solution
  • Primal-dual algorithm
• December 1
  • Parallel randomized algorithm for maximum independent set problem - description [MR 12.3, also nice notes by Eric Vigoda at http://www.cc.gatech.edu/~vigoda/7530-Spring10/MIS.pdf].
  • Parallel randomized algorithm for maximum independent set problem - analysis [MR 12.3, the notes by E. Vigoda].
• December 8
  • Derandomization of the parallel alg. for max IS using pairwise independent variables.
  • 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 15
  • Hashing
    • Perfect hashing and static dictionary with constant time per lookup in the worst case.
  • 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].
• January 5, 2026
  • Testing the existence of perfect matchings in bipartite graphs [MR 7.3 and 12.4].
  • Isolating lemma [MR 12.4].
  • Parallel randomized algorithm for a perfect matching in bipartite graphs [MR 12.4].

Material not covered

• Hashing
  • Power of two choices, statement of the results [MU 14]
• Testing the existence of perfect matchings in general graphs [MR 12.4].
• Parallel randomized algorithm for a perfect matching in general graphs [MR 12.4].

Previous run of the course in 2024

Textbooks and Study Material

Notes written by Jakub Smolík in 2025

Notes and recordings from the 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.