General information
Schedule
Contents
The overview will be continousuly updated during the course.
| Date | Lectures | Suggested reading |
|---|---|---|
| 1/2 | Introduction to the course Introduction to approximation algorithms Set Cover: IP formulation and LP relaxation Set Cover: LP-rounding |
Pizza meeting slides; More details 1.1 [WS] 1.2 [WS] 1.3-1.4 [WS]; Lecture notes |
| 2/2 | Exercises Set Cover: Primal-Dual |
Exercise sheet 1 1.4-1.5 [WS]; Lecture notes |
| 5/2 | Exercises Set Cover: Greedy |
Exercise sheet 2 1.6 [WS]; Lecture notes |
| 6/2 | Exercises Set Cover: Randomized LP-rounding |
Exercise sheet 3 1.7 [WS]; Lecture notes |
| 9/2 | This lecture will start at 8:45 TSP: Insertion and Christofide’s algorithm |
2.4 [WS]; Lecture notes |
| 12/2 | Exercises | Exercise sheet 4; Lecture notes |
| 13/2 | TSP: Heuristics | [No]; 1-4 [Be]; Slides |
| 16/2 | TSP: Heuristics | [No]; 1-4 [Be] Exercise sheet 5 |
| 19/2 | TSP: More on construction heuristics. Local search | 1-3 [Be] |
| 20/2 | TSP: Local search | Exercise sheet 6 4 [Be], ch 1, sc 2.1, 4.1 [MAK] Slides |
| 23/2 | TSP: Efficiency issues in local search + Code review | Exercise sheet 7 |
| 27/2 | Local search theory | ch 1, sc 2.1, 4.1 [MAK]; Slides |
| 2/3 | Exercises on local search design | Slides Project 1st part |
| 6/3 | Knapsack: Approximation algorithms Introduction to Bin Packing |
3.1 [WS] 3.3 [WS]; Lecture notes |
| 9/3 | Exercises Bin Packing: Approximation algorithms |
Exercise sheet 8 3.3 [WS]; Lecture notes |
| 12/3 | Bin Packing: Dyn. prg. and running time for the APTAS Working Environment |
3.3 [WS]; Lecture notes Slides |
| 13/3 | Experimental Analysis of Heuristics for Optimization | Slides |
| 19/3 | Experimental Analysis of Heuristics for Optimization: Visualization | |
| 20/3 | Experimental Analysis of Heuristics for Optimization: Testing Midway course evaluation |
Slides |
| 3/4 | Cancelled | |
| 6/4 | SAT: Local Search | Slides; Exercise sheet 9 |
| 10/4 | Stochastic Local Search & Metaheuristics (local search based) | ch 7 [MAK]; Slides |
| 13/4 | Metaheuristics (construction heuristic based) | Slides; Project 2nd part |
| 16/4 | Ant Colony Optimization | Slides |
| 17/4 | Evolutionary Algorithms | Slides; Slides |
| 19/4 | Scheduling: Approximation algorithms | 2.3 [WS]; Lecture notes |
| 23/4 | Exercises Scheduling: PTAS |
Exercise sheet 10 3.2 [WS]; Lecture notes |
| 24/4 | Scheduling: Classification | Slides; ch 1 [BK]; Exercise sheet 11 |
| 30/4 | Scheduling: Complexity | Slides [BK ch 1] [P chp 2,3] |
| 1/5 | Scheduling: Single Machine | Slides |
| 7/5 | Scheduling: Flow Shop | Slides [P sec 6.1] |
| 8/5 | Scheduling: Job Shop | Slides [P sec 7.1-7.3] [MAK sec 3.3] |
| 9/5 | Scheduling: Resource Constrained Project Scheduling | Slides [BK chp 1,3] |
| 15/5 | MAX SAT: Randomized algorithms and derandomization | 5.1-5.3 [WS]; Lecture notes |
| 18/5 | Exercises MAX SAT: LP rounding |
Exercise sheet 12 5.4-5.6 [WS]; Lecture notes |
| 22/5 | Exercise Course evalutation Discussion of the exam Assignment of exam slots |
Exercise sheet 13; Solution |
| 4/6 | Q&A session |
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
-
[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)
-
[No] Peter Norvig The Traveling Salesperson Problem: Python notebook.
-
[BK] P. Brucker, S. Knust. Complex Scheduling. Springer, 2012.
-
[P] M. L. Pinedo. Scheduling Theory, Algorithms, and Systems. Springer 2016.
Assessment and Grading
-
Oral exam based on the theoretical part and the practical project assignment. Ordinary session: June 6th. Reexams: August 28th.