Approximation Algorithms (APX)

Course content

Many optimization problems in the real world are NP-hard, meaning that we cannot hope to solve them optimally. Instead, we use approximation algorithms to find solutions that are provably close in quality to the optimal solutions.

The course is of a theoretical nature, giving the students general guidelines for developing and analysing approximation algorithms for various optimization problems. It is aimed at graduate students who like to use mathematics to solve algorithmic problems.

The topics mentioned under Learning Outcome are covered in lectures and worked on in exercises in order to develop the necessary skills and competences.



MSc Programme in Computer Science

Learning outcome

Knowledge of

  • Greedy algorithms and local search
  • Rounding data and dynamic programming
  • Deterministic rounding of linear programs
  • Random sampling and randomized rounding of linear programs
  • Randomized rounding of semidefinite programs

Skills in

  • Proving approximation guarantees for different types of algorithms
  • Using linear programming, both with rounding and as a theoretical basis for primal-dual algorithms
  • Analysing greedy algorithms and local search algorithms

Competences to

  • Apply approximation algorithms to computational problems that the student may later encounter in life.
  • Communicate effectively about the theory of approximation algorithms, both for accessing advanced topics from the research literature and for convincingly presenting the results of own work.

Lectures and compulsory assignments.

See Absalon when the course is set up.

Expected to be: "The Design of Approximation Algorithms" by Shmoys and Williamson (is available for free online)

The students should be comfortable with formal, mathematical reasoning, as the course uses the power of mathematics to understand and prove good performance of algorithms. It is assumed that the students have completed an algorithms course such as Advanced Algorithms and Data Structures, and are comfortable using mathematical proofs in the analysis of algorithms.

Academic qualifications equivalent to a BSc degree is recommended.

Continuous feedback during the course of the semester
7,5 ECTS
Type of assessment
Oral examination, 30 minutes (including grading)
The oral examination is with 30 minutes preparation
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Criteria for exam assessment

See Learning Outcome.

Single subject courses (day)

  • Category
  • Hours
  • Lectures
  • 36
  • Preparation
  • 85
  • Theory exercises
  • 84
  • Exam
  • 1
  • English
  • 206


Course number
7,5 ECTS
Programme level
Full Degree Master

1 block

Block 4
No limit
The number of seats may be reduced in the late registration period
Study Board of Mathematics and Computer Science
Contracting department
  • Department of Computer Science
Contracting faculty
  • Faculty of Science
Course Coordinator
  • Rasmus Pagh   (4-73646a6b43676c316e7831676e)
Saved on the 18-02-2022

Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students