$title = "DM833 - Lectures"; $name = "Lene Monrad Favrholdt"; $login = "lenem"; include("/home/www/Design/pre.php"); ?>
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:
|
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)