DM867: Combinatorial Optimization
Study Board of Science
Teaching language: Danish, but English if international students are enrolled
EKA: N340014102
Assessment: Second examiner: External
Grading: 7-point grading scale
Offered in: Odense
Offered in: Autumn
Level: Master
STADS ID (UVA): N340014101
ECTS value: 10
Date of Approval:
Duration: 1 semester
Version: Archive
Comment
Entry requirements
Academic preconditions
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.
Course introduction
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
The learning objective of the course is that the student demonstrates the ability to:
- 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.
Content
The following main topics are contained in the course:
- 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.
Literature
Examination regulations
Exam element a)
Timing
Autumn
Tests
Oral exam and an assignments handed-in during the course.
EKA
N340014102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
10
Additional information
The assignment, together with selected subjects from the course, forms the basis for the oral exam. Censor will be able to view the answers to the assignments.
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.
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
Teaching Method
At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
The intro phase consists of lectures by the teacher. Here we cover theory and methods and these are illustrated through examples. The intro phase is complemented by the skills training phase in which the students each week are working with new assigments covering the topics currently studied. Finally, the study phase consists of further independent reading of and reflection upon the course materials as well as solution of the two sets of problems which constitute the exam.
Activities during the study phase:
- 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.