MAT-72606 Approximation Algorithms, 4 cr
Additional information
No lectures in the academic year 2017-2018.
Suitable for postgraduate studies.
The implementation will not be executed during the academic year 2017-2018.
Person responsible
Tapio Elomaa
Lessons
| Implementation | Period | Person responsible | Requirements |
| MAT-72606 2017-01 | - |
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:
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