General information
Schedule
Contents
The overview will be continuously updated during the course.
| Week | Date | Lectures | Suggested reading |
|---|---|---|---|
| 6 | 5/2 | Introduction to the course Introduction to approximation algorithms TSP: Insertion and the Double Tree algorithm |
Pizza meeting slides; More details 1.1 [WS] 2.4 [WS]; Lecture notes |
| 7/2 | TSP: Christofide’s algorithm Exercises |
2.4 [WS]; Lecture notes Exercise sheet 1 |
|
| 7 | 12/2 | TSP: Heuristics | [No]; Slides; wiki |
| 13/2 | TSP: Heuristics | [No]; sc. 1-3 [Be] | |
| 14/2 | Exercises | Exercise sheet 2 | |
| 8 | 19/2 | TSP: Local search | sc. 4 [Be], ch 1, sc 2.1, 4.1 [MAK] Slides |
| 20/2 | TSP: Efficiency issues in local search | ||
| 21/2 | Exercises on local search for TSP | Exercise sheet 3 | |
| 9 | 27/2 | Local search theory | ch 1, sc 2.1, 4.1 [MAK] Slides |
| 28/2 | SAT: Local Search | Exercise sheet 4 Slides | |
| 10 | 5/3 | MAX SAT: Randomized algorithms and derandomization | 5.1-5.3 [WS]; Lecture notes |
| 7/3 | Exercises MAX SAT: randomized LP rounding and Best of Two |
Exercise sheet 5 5.4-5.5 [WS]; Lecture notes |
|
| 11 | 12/3 | Q&A on the project assignment and Sheet 4 MAT SAT: Best of Two and nonlinear randomized LP rounding |
Project part 1; Slides 5.5-5.6 [WS]; Lecture notes |
| 14/3 | Set Cover: deterministic LP-rounding Set Cover: LP duality |
1.2-1.3 [WS] 1.4 [WS]; Lecture notes |
|
| 12 | 19/3 | Exercises Set Cover: Primal-Dual algorithm |
Exercise sheet 6 1.4-1.5 [WS]; Lecture notes |
| 21/3 | Set Cover: Randomized LP-rounding Set Cover: Greedy |
1.7 [WS] 1.6 [WS]; Lecture notes |
|
| 13 | 26/3 | Exercises Set Cover: Greedy analyzed by Dual Fitting |
Exercise sheet 7 1.6 [WS]; Lecture notes |
| 28/3 | Lecture cancelled | ||
| 14 | 2/4 | Experimental Analysis of Heuristics for Optimization | Slides |
| 4/4 | Experimental Analysis of Heuristics for Optimization: Visualization | Slides | |
| 15 | 9/4 | Experimental Analysis of Heuristics for Optimization: Testing Midway course evaluation |
|
| 11/4 | Stochastic Local Search & Metaheuristics (local search based) | Slides; ch 7 [MAK] | |
| 16 | Easter | ||
| 17 | 23/4 | Metaheuristics (construction heuristic based) | Slides; Project part 2 |
| 24/4 | Ant Colony Optimization | Slides | |
| 25/4 | Evolutionary Algorithms | Slides | |
| 18 | 30/4 | Evolutionary Algorithms Knapsack: Approximation algorithms |
3.1 [WS]; Lecture notes |
| 2/5 | Knapsack: FPTAS Exercise Bin Packing: Approximation algorithms |
3.1 [WS] Exercise sheet 8 3.3 [WS]; Lecture notes |
|
| 19 | 7/5 | Exercise Bin Packing: APTAS |
Exercise sheet 9 3.3 [WS]; Lecture notes |
| 9/5 | Scheduling: Classification | Slides; Slides; Exercise sheet 10; ch 1 [BK] | |
| 20 | 13/5 | Scheduling: Complexity | Slides; [BK ch 1] [P chp 2,3] |
| 15/5 | Scheduling: Single Machine | Slides; | |
| 21 | 21/5 | Scheduling: Approximation algorithms | 2.3 [WS]; Lecture notes |
| 23/5 | Scheduling: PTAS Exercises |
3.2 [WS]; Lecture notes Exercise sheet 11 |
|
| 22 | 28/5 | Course evalutation Discussion of the exam Assignment of exam slots |
All lecture notes for approximation algorithms as one pdf-file Q&A |
References
-
[WS] David P. Williamson and David B. Shmoys. Design of Approximation Algorithms. Cambridge University Press. 2010.
-
[MAK] W. Michiels, E. Aarts and J. Korst. Theoretical Aspects of Local Search. Springer Berlin Heidelberg, 2007
-
[No] Peter Norvig The Traveling Salesperson Problem: Python notebook.
-
[Be] J.J. Bentley. Fast Algorithms for Geometric Traveling Salesman Problems. ORSA Journal on Computing, 1992, vol. 4, issue 4, pp. 387-411 (Available in BlackBoard Course Materials)
-
[BK] P. Brucker, S. Knust. Complex Scheduling. Springer, 2012.
-
[P] M. L. Pinedo. Scheduling Theory, Algorithms, and Systems. Springer 2016.
Assessment and Grading
-
Practical assignments.
-
Oral exam based on the theoretical part and the practical assignments. Ordinary exam in June. Reexams in August. Guidelines.