MAT-72606 Approximation Algorithms, 4 cr

Additional information

Suitable for postgraduate studies.

Person responsible

Tapio Elomaa

Lessons

Implementation Period Person responsible Requirements
MAT-72606 2016-01 4 Tapio Elomaa

Learning Outcomes

After completion of the course the student will appreciate the approach of approximating the solution of computationally difficult problems. Examples of combinatorial algorithms and linear programming based algorithms are familiar for the student.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Greedy algorithms and local search     
2. Rounding data and dynamic programming     
3. Deterministic rounding of linear programs     
4. Random sampling     
5. Randomized rounding of semidefinite programs     
6. The primal-dual method     

Instructions for students on how to achieve the learning outcomes

The assessment is based on an exam.

Assessment scale:

Numerical evaluation scale (0-5)

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Additional information Examination material
Book   The Design of Approximation Algorithms   David P. Williamson & David B. Shmoys         Yes   

Prerequisites

Course Mandatory/Advisable Description
MAT-02650 Algoritmimatematiikka Mandatory    
TIE-02100 Johdatus ohjelmointiin Mandatory    

Correspondence of content

There is no equivalence with any other courses

Updated by: Ikonen Suvi-Päivikki, 13.04.2016