Approximation Algorithms, Copenhagen University, Spring 2021

Prerequisites: Students should be comfortable with formal, mathematical reasoning, as the course uses the power of mathematics to understand and prove good performance of algorithms. It is assumed that students have completed an algorithms course, and are comfortable using mathematical proofs in the analysis of algorithms.

Lecturer: Rasmus Pagh

Literature:

• WS = Williamson and Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010. An electronic version can currently be downloaded free of charge at: https://www.designofapproxalgs.com/.
• CY = Cormode and Yi. Small Summaries for Big Data. Cambridge University Press, 2020. An electronic version can currently be downloaded free of charge at: http://dimacs.rutgers.edu/~graham/ssbd.html.
• R = Roughgarden. CS 261: A Second Course in Algorithms, 2016. Course notes available for download at: http://timroughgarden.org/w16/w16.html.

Colabs

• Vertex cover
• Correlation clustering
• HyperLogLog

Lectures:

• 2021-04-27 Greedy algorithms and local search. WS 1.1, 2.1, 2.2, 2.3, 2.4. Lecture slides, video.
• 2021-04-29 Rounding data and dynamic programming. WS [3.1], 3.2, 3.3. Lecture slides, video.
• 2021-05-04 Linear programming and deterministic rounding. Roughgarden lecture #7, sec. 1+2. WS 1.2-1.3, 4.3 (until "We now turn to..."), 4.4. Lecture slides, code, video.
• 2021-05-06 Random sampling and randomized rounding of linear programs. WS 1.7, 5.1, 5.2, 5.4. Lecture slides, video.
• 2021-05-11 Randomized rounding of semidefinite programs. WS 6.1, 6.2, 6.4. Lecture slides, code, video.
• 2021-05-18 The primal-dual method. WS 7.0, 7.2-7.4. Lecture slides, video.
• 2021-05-20 The multiway cut problem. Hardness of approximation. WS 8.1, 8.2 (and reading from previous lectures). Lecture slides, video.
• 2021-05-25 Random sampling, priority sampling. CY 1.4 and CY 2.2, 2.3, 2.4 (skip part of "Further discussion" in sec. 2.3 after "Average variance"). Lecture slides, video.
• 2021-05-27 Cardinality estimation. CY chapter 2, section 2.5, 2.6, 2.7. Lecture slides, video.
• 2021-06-01 Summaries for multisets. CY chapter 3, section 3.2, 3.3, 3.4. Lecture slides, video.
• 2021-06-03 Summaries for ordered data. CY chapter 4, section 4.0, 4.1, 4.3, 4.4. Lecture slides, video.
• 2021-06-08 Multiplicative weights. Roughgarden lecture #11, sections 1-4. Lecture slides, Video introduction (no audio) and lecture by Roughgarden (until 1:08:00).
• 2021-06-10 On-line algorithms I. Roughgarden lecture #13. Lecture slides, video.
• 2021-06-15 On-line algorithms II. Roughgarden lecture #14. Lecture slides, video.

The course materials are licensed under a Creative Commons Attribution 4.0 International License.