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
Lene Monrad Favrholdt, Lektor, Ph.d.
Tlf.: 6550 2341 Email: lenem@imada.sdu.dk

Timetable
Group Type Day Time Classroom Weeks Comment
Common I Monday 12-14 IMADA Seminarrum 15-22
Common I Tuesday 12-14 IMADA Seminarrum 15-22
Common I Friday 12-14 IMADA Seminarrum 15-22
Show entire timetable
Show personal time table for this course.

Prerequisites:
None

Academic preconditions:
The contents of 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.

Expected learning outcome
After 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 overview
Combinatorial algorithms, LP-based algorithms, vertex cover, set
cover, TSP, multiway cut, k-center, knapsack, bin packing,
scheduling.

Literature
There isn't any litterature for the course at the moment.

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)

Date of exam
The ordinary exam takes place on June 6, 2014
The re-examination takes place on August 22, 2014

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.