NDMI084 Introduction to approximation and randomized algorithms

Winter semester 2024/25

Petr Kolman, Jiří Sgall

The weekly lecture takes place every Thursday in Lecture room S5 (Mala Strana) from 2:00 - 3:30 pm. The tutorials take place once in two weeks on Monday, 2:00 - 2:30 pm, in S8, and are led by Cyril Kotecký.

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, 2024
  • 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].
  • Greedy algorithms: 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].
  • Greedy algorithm for edge disjoint paths in graphs - introduction [KT 11.5].
• November 7
  • 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 14
  • 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].

Tentative Schedule

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

• November 21
• Algorithms for MAX SAT [WS 5.1-5.5, V 16].
  
  • 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
  • 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].
• 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, 2025
• 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].

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.

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