Courses Master Display 2018-2019

Course Description To PDF
Course title Algorithms and Optimisation
Course code EBC4049
ECTS credits 6,5
Assessment None
Period
Period Start End Mon Tue Wed Thu Fri
2 29-10-2018 21-12-2018 X X
Level Advanced
Coordinator Alexander Grigoriev
For more information: a.grigoriev@maastrichtuniversity.nl
Language of instruction English
Goals
Ability to analyse the complexity of optimization problems, and ability to design fast algorithms providing good-quality solutions for hard optimization problems.
Description
This course is devoted to mathematical models and solution methods for hard optimization problems. First, we study the theory of computational complexity, including the concept of P versus NP. In particular, we prove that some problems are computationally intractable. Given the complexity insights, solving such problems is a challenge. Therefore, we study the design and analysis of approximation algorithms and approximation schemes, as well as the derivation of inapproximability results. We also discuss local search frameworks such as Simulated Annealing, Genetic Algorithms and Tabu Search. The course is open ended in the sense that some topics can be chosen according to student interests. Classical problems that will be covered are, among others, scheduling, colouring, set covering, and packing.
Literature
"Algorithms" by Dasgupta, Papadimitriou and Vazirani (Mc Graw-Hill).
Selected chapters from several books on combinatorial optimization.
Research papers.
Prerequisites
Students need to have obtained a Bachelor degree in Econometrics, Operations Research, Mathematics, or Computer Science. Knowledge in optimization (Linear Programming) and basic graph theory is highly recommended. Familiarity with basic algorithms and the analysis of algorithms (runtime complexity) is certainly helpful. C++ (or Java/Python/Basic) Programming skills are also prerequisites as there will be a practical programming case.
An advanced level of English.
Teaching methods (indicative; course manual is definitive) PBL / Lecture / Assignment / Groupwork
Assessment methods (indicative; course manual is definitive) Participation / Written Exam
Evaluation in previous academic year For the complete evaluation of this course please click "here"
This course belongs to the following programmes / specialisations
Master Business Research Methodology Electives
Master Business Research - Operations Research Compulsory Courses
Master Business Research - Operations Research Methodology Electives
Master Econometrics and Operations Research Econometrics & OR Electives
Master Econometrics and Operations Research Operations Research
SBE Non Degree Courses Master Courses