DM833: Approximation Algorithms (5 ECTS)
STADS: 15009601Level
Master's level course approved as PhD course
Teaching period
The course is held twice a year, once in the autumn semester and once in the spring semester.
The course is offered when needed
Teacher responsible
Email: lenem@imada.sdu.dkTimetable
There is no timetable available for the chosen semester.
Comment:
Ubegrænset deltagerantal.
Prerequisites:
None
Academic preconditions:
Students taking the course are expected to:
- The contents of DM553: Complexity and Computability or DM508: Algorithms and Complexity must be known.
Course introduction
The 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.
The course provides the basis for a specialization in the subject, e.g. in the master thesis.
The course provides the basis for a specialization in the subject, e.g. in the master thesis.
Expected learning outcome
The learning objectives of the course is that the student demonstrates the ability 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.
- explain the concepts of pseudo-polynomial and strongly NP-hard and give examples.
- explain the concepts of PTAS, asymptotic PTAS, and FPTAS, with examples.
- describe similarities and differences between different LP-techniques.
Subject overview
The following main topics are contained in the course:
- Combinatorial algorithms, LP-based algorithms, vertex cover, set cover, TSP, multiway cut, k-center, knapsack, bin packing, scheduling.
Literature
- Meddeles ved kursets start.
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).
The teaching method is based on three phase model.
Intro phase: 22 hours
Skills training phase: 20 hours, hereof:
- Tutorials: 20 hours
Educational activities
Educational form
In the intro phase, concepts, theories and models are introduced and put into perspective. In the training phase, students train their skills through exercises and dig deeper into the subject matter. In the study phase, students gain academic, personal and social experiences that consolidate and further develop their scientific proficiency. Focus is on immersion, understanding, and development of collaborative skills.
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.
