DM867: Combinatorial Optimization
Students taking the course are expected to:
- Have basic data structures and graph algorithms such as those taught in DM507
- Have knowledge about problem complexity, including the complexity classes P and NP, as well as basic approximation algorithms corresponding to those covered in DM553.
- Having a basic knowledge about linear programming and flows in networks (e.g. from DM817) is an advantage but is not a prerequisite as we will introduce the necessary things in the course.
The aim of the course is to enable the student to:
- Apply theory and methods from combinatorial optimization to reason about problems of a combinatorial nature.
- Develop efficient algorithms for solving practical problems which are similar in nature to those studied in the course.
Be able to argue that a combinatorial optimization problem is NP-hard and suggest methods for obtaining approximate solutions via methods learned in the course.
- Develop new theory and methods for combinatorial optimization problems which are related to those studied in the course.
The course builds on the knowledge acquired in the courses DM507 and DM553.
The course gives a foundation for doing a master thesis within combinatorial optimization and graph algorithms.
In relation to the competence profile of the degree it is the explicit focus of the course to enable the students to
- Analyse and solve advanced problems within combinatorial optimization by applying the methods from the course.
- Be able to solve practical optimization problems by using the methods from the course.
- Develop new variants of the methods studied in the course in order to apply these to new types of problems.
Expected learning outcome
- Apply the theory from the course as a tool to solve problems which resemble those from the course.
- Apply algorithms from the course as subroutines in more complex algorithms.
- Apply algorithms and theory from the course to solve practical optimization problems.
- Identify and argue about combinatorial optimization problems from a description of such in words.
- Evaluate whether a given combinatorial optimization problem, similar in nature to those studied in the course, can be solved efficiently or is P-hard.
- Apply algorithmic methods based on tree decompositions of graphs.
- Matchings in graphs and generalizations of these.
- Matroids and their applications in combinatorial optimization.
- Branchings in digraphs.
- Graph connectivity.
- Integer programming.
- Approximation algorithms.
- Multicommodity flows and disjoint paths.
- Tree decompositions of graphs with algorithmic applications.
- Parametrized complexity.
- NP-completeness proofs.
- Chordal graphs.
Exam element a)
Oral exam and an assignments handed-in during the course.
Re-examination in the same exam period or in immediate extension. Reeksamen is an oral exam, which is graded according to the 7th grade and external examiner.
Indicative number of lessons
- Solution of weekly assignments in order to discuss these at the exercise sections
- Solving the project assignments
- Self study of various parts of the course material.
- Reflection upon the intro and training sections.