DM865 - Heuristics and Approximation Algorithms

General information

Schedule

MitSDU

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

Assessment and Grading

Course Evaluation