Course Catalog 2014-2015
Basic

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

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
Lectures
Excercises


 


 


 
 4 h/week
 2 h/week


 
MAT-72606 2014-01 Tuesday 12 - 14 , TB219
Thursday 12 - 14 , TB223

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:

Completion parts must belong to the same implementation

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
MAT-72606 2014-01 Spring 2015        

Last modified06.03.2014