General information
Schedule
Contents
The overview will be continuously updated during the course.
| Week | Date | Lectures | Suggested reading |
|---|---|---|---|
| 6 | 3/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 |
| 5/2 | TSP: Christofide’s algorithm Exercises |
2.4 [WS]; Lecture notes Exercise sheet 1 |
|
| 7 | 10/2 | TSP: Heuristics | [No]; Slides; wiki |
| 12/2 | TSP: Heuristics | [No]; sc. 1-3 [Be] | |
| 14/2 | Exercises | Exercise sheet 2 | |
| 8 | 17/2 | TSP: Local search | sc. 4 [Be]; ch 1, sc 2.1, 4.1 [MAK]; Slides |
| 19/2 | TSP: Efficiency issues in local search | ||
| 21/2 | Exercises on local search for TSP | Exercise Sheet 3 | |
| 9 | 24/2 | SAT: Local Search | Slides; Exercise sheet 4 |
| 26/2 | Local search theory | ch 1, sc 2.1, 4.1 [MAK]; Slides | |
| 28/2 | MAX SAT: Randomized algorithms and derandomization | 5.1-5.3 [WS]; Lecture notes | |
| 10 | 2/3 | Exercises MAX SAT: randomized LP rounding and Best of Two |
Exercise sheet 5 5.4-5.5 [WS]; Lecture notes |
| 4/3 | Q&A on the project assignment and Sheet 4 Midway course evaluation |
Project part 1; | |
| 11 | 9/3 | MAX SAT: Nonlinear randomized LP rounding Set Cover: deterministic LP-rounding |
5.6 [WS]; Lecture notes 1.2-1.3 [WS] |
| 11/3 | Exercises Set Cover: LP duality |
Exercise sheet 6 1.4 [WS]; Lecture notes |
|
| 12 | 16/3 | Set Cover: Primal-Dual algorithm | 1.4-1.5 [WS]; Lecture notes |
| 18/3 | Set Cover: Greedy analyzed by Dual Fitting | 1.6 [WS]; Lecture notes | |
| 13 | 23/3 | Set Cover: Randomized LP-rounding Exercises |
1.7 [WS]; Lecture notes Exercise sheet 7 |
| 25/3 | Experimental Analysis of Heuristics for Optimization | Slides; Slides | |
| 14 | 30/3 | Experimental Analysis of Heuristics for Optimization: Visualization | Classwork |
| 1/4 | Experimental Analysis of Heuristics for Optimization: Testing | Slides | |
| 15 | Easter | ||
| 16 | 14/4 | Experimental Analysis of Heuristics for Optimization: Testing | |
| 15/4 | Stochastic Local Search & Metaheuristics (local search based) | Slides; ch 7 [MAK]; Project part 2 | |
| 17 | 20/4 | Metaheuristics (construction heuristic based) | Slides |
| 22/4 | Ant Colony Optimization | Slides | |
| 24/4 | Evolutionary Algorithms | Slides | |
| 18 | 27/4 | Knapsack: Approximation algorithms & FPTAS Bin Packing: Approximation algorithms |
3.1 [WS]; Lecture notes 3.3 [WS] |
| 29/4 | Exercises Bin Packing: APTAS |
Exercise sheet 8 3.3 [WS]; Lecture notes |
|
| 19 | 4/5 | Scheduling: Classification | Slides; Exercise sheet 9; ch 1 [BK] |
| 6/5 | Scheduling: Complexity | Slides; | |
| 20 | 11/5 | Scheduling: RCPSP | Slides; [BK ch 1] [P chp 2,3] |
| 13/5 | Scheduling: Approximation algorithms | 2.3 [WS]; Lecture notes | |
| 15/5 | Canceled due to very few participants | ||
| 21 | 18/5 | Exercises Scheduling: PTAS Discussion of the exam |
Exercise sheet 10 3.2 [WS]; Lecture notes All lecture notes for approx. algorithms as one pdf-file |
| 20/5 | Assignment of exam slots Course evaluation Exam simulation |
List padlet |
|
| 22 | 27/5 | Question Time & Technical preparation for the exam | 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 on the 2nd of June 2020 (online). Reexam on the 19th of August 2020. Guidelines.