Study of some fundamental combinatorial optimization problems: algorithms, complexity and applications.
Algorithms: Maxflow-mincut-theorem. Primal-dual method for linear programming, with applications to network flows. Efficient algorithms for maxflow problems. Matching. Minimal spanning trees. Matroids.
Complexity: NP-completeness, foundations and relevant examples.
Applications: Heuristic methods for some interesting problem classes.
That the student should obtain a deep understanding of the mathematical theory and some practical algorithms for combinatorial optimization.
After completed course, the student should be able to
A Master degree including at least 30 university credits (hp) in in Mathematics (Calculus, Linear algebra, Differential equations and transform method), and further at least 6 hp in Mathematical Statistics, 6 hp in Numerical analysis and 6 hp in Optimization.
Suitable prerequisites is the courses SF2812 Applied Linear Optimization or similar knowledge.
Announced when the course is offered.
If the course is discontinued, students may request to be examined during the following two academic years.
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
The examination is by homework assignments and a final oral exam.
Homework assignments and a final oral exam.
