|
|
|||||||||||||||||
Course Catalog 2014-2015
MAT-72606 Approximation Algorithms, 4 cr |
Additional information
Suitable for postgraduate studies
Person responsible
Tapio Elomaa
Lessons
| Study type | P1 | P2 | P3 | P4 | Summer | Implementations | Lecture times and places |
|
|
|
|
|
|
|
|
|
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 | Edition, availability, ... | Examination material | Language |
| Book | The Design of Approximation Algorithms | Williamson and Shmoys | 9780511921735 | No | English |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-02650 Algoritmimatematiikka | Mandatory | |
| TIE-02100 Johdatus ohjelmointiin | Mandatory |
Prerequisite relations (Requires logging in to POP)
Correspondence of content
There is no equivalence with any other courses
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |
| Spring 2015 |