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 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
  • 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.