DM833: Approximation Algorithms (5 ECTS)
STADS: 15009601
Level
Master's level course
Teaching period
The course is offered in the spring semester.
The course is offered when needed
Teacher responsible
Email: lenem@imada.sdu.dk
Timetable
Group |
Type |
Day |
Time |
Classroom |
Weeks |
Comment |
Common |
I |
Monday |
08-10 |
Spørg underviseren |
15-20,22 |
|
Common |
I |
Tuesday |
10-12 |
Spørg underviseren |
15-22 |
|
Common |
I |
Wednesday |
10-12 |
Spørg underviseren |
15-22 |
|
Show entire timetable
Show personal time table for this course.
Comment:
Ubegrænset deltagerantal. 4. kvartal.
Prerequisites:
None
Academic preconditions:
The contents of DM508 - Algorithms and Complexity must be known.
Course introductionThe field of approximation algorithms has developed in response to the difficulty in solving important optimization problems to optimality. In contrast to heuristics, approximation algorithms come with a guaranteed running time and solution quality. As a simple example, consider the greedy algorithm which gives a vertex cover with
at most twice as many vertices as an optimal vertex cover. In this course, we will study approximation algorithms, with a number of NP-hard problems as example problems.
Expected learning outcomeAfter the course, the student is expected to be able to
- give an overview of the problems and techniques studied in the
course.
- give a precise definition of each of the combinatorial problems
studied in the course.
- give a precise description and analysis of each of the algorithms
studied in the course.
Subject overviewCombinatorial algorithms, LP-based algorithms, vertex cover, set
cover, TSP, multiway cut, k-center, knapsack, bin packing,
scheduling.
Literature- Vijay V. Vazirani: Approximation Algorithms.
Website
This course uses
e-learn (blackboard).
Prerequisites for participating in the exam
None
Assessment and marking:
Oral exam. Danish 7 mark scale, external examiner (5 ECTS). (15009602)
Expected working hours
The teaching method is based on three phase model.
Intro phase: 22 hours
Skills training phase: 20 hours, hereof:
- Tutorials: 20 hours
Educational activities
Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.
Course enrollment
See deadline of enrolment.
Tuition fees for single courses
See fees for single courses.