# DM865 - Heuristics and Approximation Algorithms

MitSDU

## Contents

The overview will be continuously updated during the course.

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

• Practical assignments.

• Oral exam based on the theoretical part and the practical assignments. Ordinary exam in June. Reexams in August. Guidelines.