
DM833  Approximation Algorithms
Spring 2014
Lene Monrad Favrholdt
Lectures
Tentative outline:
Date 
Contents 
Monday, April 7 
Section 1.01.1: Introduction to approximation algorithms, with
Vertex Cover as an example

Tuesday, April 8 
Section 2.02.1: Set Cover and the Greedy Algorithm
Exercise 1.1

Friday, April 11 
Section 3.2: TSP
Exercises

Monday, April 14 
Thm 3.6 in Section 3.2
Section 3.1: Steiner Tree
Exercises 2.1, 2.2, and 2.8
In Exercise 2.2, is the lower bound of 1/2 tight?

Tuesday, April 15 
Easter holiday 
Friday, April 18 
Easter holiday 
Monday, April 21 
Easter holiday 
Tuesday, April 22 
Section 4.1: Multiway cut
Exercise 2.8 and the following exercises

Friday, April 25 
Canceled 
Monday, April 28 
Sections 5.05.1: The kCenter problem and parametric pruning
Exercises 
Wednesday, April 30 
Theorem 5.7
Exercise 4.2
Chapter 8: Knapsack

Friday, May 2 
Institutdysten 
Tuesday, May 6 
Canceled 
Wednesday, May 7 
Canceled 
Friday, May 9 
We will finish Chapter 8 and begin
Chapter 9: Binpacking
Exercises:
 Describe an efficient implementation of Algorithm 5.3.
Hint: Is it necessary to construct the square of G_j explicitly?
 Exercise 5.1

Monday, May 12 
Section 9.1: An asymptotic PTAS for bin packing
Exercises 8.1 and 8.2

Wednesday, May 14 
Parts of Sections 12.1 and 12.3
Section 13.1: Dual Fitting applied to Set Cover
Exercises 
Friday, May 16 
General Prayer Day 
Tuesday, May 20 
A short recap of Section 13.1 up to Lemma 13.2
Lemma 13.2 and Thm 13.3
Section 13.2: Dual Fitting applied to Constrained Set Multicover
Exercises 
Wednesday, May 21 
Section 13:2: Dual Fitting applied to Constrained Set Multicover
Chapter 14: LPRounding Applied to Set Cover
Exercises 13.1, 13.2, and 13.3 
Friday, May 23 
We will finish Chapter 14
If time permits, we will begin Chapter 15
Exercise 13.4.1 
Monday, May 26 
Chapter 15: The PrimalDual schema applied to Set Cover
Exercises

Wednesday, May 28 
Exercises

Friday, May 30 
Canceled 
Weekly notes (summarizing the above information in a pdffile)

