NDAK16001U CANCELLED Approximation Algorithms (APX)

Volume 2016/2017
Education

MSc programme in Computer Science

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

 

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
  • The primal-dual method
  • Cuts and metrics
  • Further uses of the different techniques in various application areas


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

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

It is assumed that the students have completed an algorithms course such as Advanced Algorithms and Data Structures, and are comfortable with the idea of mathematical proofs about the correctness of algorithms. Knowledge of basic probability theory (e.g., how to compute the expected value of a discrete random variable) is recommended.
Lectures and compulsory assignments
  • Category
  • Hours
  • Exam
  • 1
  • Lectures
  • 36
  • Preparation
  • 85
  • Theory exercises
  • 84
  • Total
  • 206
Credit
7,5 ECTS
Type of assessment
Oral examination, 30 minutes
30 minutes preparation, 30 minutes oral examination, including grade determination.
Exam registration requirements

The student must solve mandatory exercises during the course. Assignments will be made each week and be due in the following week. 5 out of 7 assignments must be completed by the due date and approved to qualify to take the exam.

Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
No external censorship
Several internal examiners
Re-exam

Same as ordinary exam.

If the student is not yet qualified, then qualification can be achieved by hand-in and approval of equivalent exercises. The assignments must be submitted no later than two weeks before the re-exam date.

 

Criteria for exam assesment

See learning outcome.