DM833 - Approximation Algorithms

Spring 2014
Lene Monrad Favrholdt

Lectures

Tentative outline:

Date Contents
Monday, April 7 Section 1.0-1.1: Introduction to approximation algorithms, with Vertex Cover as an example
Tuesday, April 8 Section 2.0-2.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.0-5.1: The k-Center 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: LP-Rounding 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 Primal-Dual schema applied to Set Cover
Exercises
Wednesday, May 28 Exercises
Friday, May 30 Canceled

Weekly notes (summarizing the above information in a pdf-file)