MAT-72606 Approximation Algorithms, 4 cr
Additional information
Next implementation round in Spring 2017
Suitable for postgraduate studies
Will not be lectured year 2015-2016
Person responsible
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 (1-5) will be used on the course
Partial passing:
Study material
| Type | Name | Author | ISBN | URL | Additional information | Examination material |
| Book | The Design of Approximation Algorithms | Williamson and Shmoys | 9780511921735 | No |
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