Approximation Algorithms

Advanced Course in Summer 2018

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 bounds on their worst case performances.


Dr. Ruben Hoeksma (Email)
Prof. Dr. Nicole Megow (Email)
Time & Room:

Mon 14-16 in room MZH 1090
Thu 10-12 Uhr in room MZH 1110
Thursday, April 5, 2018
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 online version
Date Topic Material & suggested reading Exercises
05/04/18 Introduction, greedy algorithms: k-center problem and load balancing slides, notes, Sections 2.2 & 2.3 of [WS] --
09/04/18 Greedy algorithms: scheduling with due dates, set cover problem slides, notes, Sections 2.1 & 1.6 of [WS] Exercise 1
12/04/18 set cover (cont.), metric TSP (double tree and Christofides' Alg.), hardness of approximation for TSP (gap reduction) slides, Section 2.4 of [WS] --
19/04/18 local search, load balancing, k-median slides, notes, Section 2.3 and 9.2 of [WS] --
23/04/18 PTASs, bin packing, load balancing slides, notes, Section 3.1 and 3.2 and Appendix B of [WS] --
26/04/18 PTAS for ETSP notes, Section 10.1 of [WS] Exercise 2
07/05/18 Linear programming and rounding, scheduling with release dates slides, notes, Section 4.1 and 4.2 of [WS] Exercise 3
14/05/18 LP rounding, Prize-collecting steiner treex slides, notes, Section 4.3 and 4.4 of [WS] --
17/05/18 LP Duality, Exercise 3 slides, Appendix A of [WS] --
24/05/18 Exercise 3, LP-rounding, uncapacitated facility location slides, notes, Section 4.5 of [WS] --
28/05/18 Random sampling, Max SAT, Max CUT notes, Section 5.1, 5.2 and 5.3 of [WS] --
31/05/18 Randomized rounding, the best of two algorithms, Max SAT notes, Section 5.4, 5.5 and also 5.6 of [WS] Exercise 4
04/06/18 Scheduling by alpha-points, randomized alpha points, 1|r_j|sum (w_j)C_j notes, article (slightly different algorithm formulation) --
11/06/18 LP Rounding, prize-collecting steiner tree, uncapacitated facility location, Chernoff bounds, multicommodity flow slides, notes, Section 5.7, 5.8, 5.10, and 5.11 of [WS] Exercise 5
14/06/18 Primal-dual algorithms, set cover, shortest path, knapsack cover slides, notes, Section 7.1, 7.3, and 7.5 of [WS] --
18/06/18 Primal-dual algorithms, uncapacitated facility location, prize-collecting steiner tree slides, notes, Section 7.6 and 14.1 of [WS] Exercise 6
21/06/18 Exercise session
25/06/18 Introduction to online optimization, ski rental, lost cow problem, doubling, list update notes
28/06/18 Online list update, summary notes
We thank Jannik Matuschke for generously sharing his slides from his course on Approximation Algorithms.