Approximation Algorithms

Master Course in Summer 2019
03-ME-602.99a, 6 CP

A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be modeled as combinatorial optimization problems. In most cases, these problems are computationally intractable and one often resorts to heuristics that provide sufficiently good solutions in reasonable amount of runtime. However, in most cases, such heuristics do not provide a worst case guarantee on the performance in comparison to the optimum solution. In this course, we shall study algorithms for combinatorial optimization problems which can provide strong mathematical guarantees on performance. The course aims at developing a toolkit for solving such problems. The lectures will consist of designing polynomial-time algorithms and proving rigorous bounds on their worst case performances.


Dr. Martin Böhm (Email)
Dr. Ruben Hoeksma (Email)
Prof. Dr. Nicole Megow (Email)
Time & Room:

Tue 12-14 in room MZH 6210
Thu 12-14 in room MZH 6210
Tuesday, April 2, 2019
The examination will be by individual oral exam. A 1/3 mark bonus is awarded to students who correctly solve 60% of the homework exercises.
Literature: The course is based on parts of the literature below and recent research articles that will be added later.
  • [WS] The Design of Approximation Algorithms, David P. Williamson and David B. Shmoys online version
  • [V] Approximation Algorithms, Vijay V. Vazirani
  • [GM] Approximation Algorithms and Semidefinite Programming, Bernd Gärtner and Jiří Matoušek, Springer, 2012.
Date Topic Material & suggested reading Homework
02/04/19 Introduction, greedy algorithms: k-center problem and load balancing orga, slides, notes, Sections 2.2 & 2.3 of [WS] --
04/04/19 Greedy algorithm for Set Cover, refresher on NP-completeness. slides, notes, Sections 1.6 & Appendix B of [WS] --
09/04/19 Exercise session 1: hardness of approximation for k-center, analysis of greedy algorithms. Exercise sheet HW Set 1, deadline 23/04 12:00.
11/04/19 TSP and Christofides' algorithm. slides, Section 2.4 of [WS] --
23/04/19 Local search: identical parallel machines and k-median. slides, notes, Sections 2.3 and 9.2 of [WS] HW Set 2, deadline 30/04 12:00.
25/04/19 Exercise session 2: polynomial run time for k-median, local search for uncapacitated facility location. Exercise sheet, Section 9.2 and 9.3 of [WS]
30/04/19 A quick refresh/intro to linear programming; deterministic rounding for approximation algorithms. slides.
02/05/19 Refresh/intro to LP duality; minimizing sum of completion times. slides.
07/05/19 Exercise session 3: LPs, separation oracles. Exercise sheet.
09/05/19 Weighted sum of completion times, approximating SAT with fair coin flipping. slides. HW Set 3, deadline 16/05 12:00.
14/05/19 Max SAT via biased coins and via randomized non-linear LP rounding. Section 5.3 and 5.6 of [WS]
16/05/19 Exercise session 4: Card tricks and directed cut. Exercise sheet. HW Set 4, deadline 23/05 12:00 (paper), 23:59 (email).
21/05/19 LP modeling. Slides.
23/05/19 Rounding the Price collecting steiner tree LP. Slides, Notes, Section 4.4 and 5.7 of [WS] .
28/05/19 Exercise session 5: Integrality gaps. Exercise sheet. HW Set 5, deadline 11/06 12:00.
30/05/19 -- 07/06/19 No lectures
11/06/19 Knapsack cover integrality gap and online optimization. Notes, proof of Theorem 2.1 of this paper.
13/06/19 PTAS for the Knapsack and P||Cmax problems. Slides, Section 3 of [WS].
18/06/19 PTAS for Euclidean TSP. Slides, Notes, Section 10.1 of [WS]. HW Set 6, deadline 27/06 12:00.
20/06/19 Semidefinite programming and rounding for Max Cut. Slides, notes, Chapters 1 and 2 of [GM]; Section 6.1 and 6.2 of [WS].
24/06/19 Coloring 3-colorable graphs with SDPs. Slides, Chapter 9 of [GM].
27/06/19 Finishing vector colorings, how to use Wigderson's trick. HW Set 7, deadline 09/07 12:00 (paper), 23:59 (email).
02/07/19 The Primal-dual method. Slides, Section 7.1 and 7.3 of [WS].
04/07/19 The Primal-dual method 2. Slides, Section 7.5 and 14.1 of [WS].
09/07/19 Exercise session 6: Primal-dual algorithms. Exercise sheet.