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: Spring
Level: Master

STADS ID (UVA): N340014101
ECTS value: 10

Date of Approval: 11-10-2021


Duration: 1 semester

Version: Approved - active

Entry requirements

None

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/MM850.
  • Having a basic knowledge about linear programming and flows in networks (e.g. from DM551/MM851 or 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, DM551/MM851 and DM553/MM850.

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.
  • Orientations of graphs.
  • Integer programming.
  • Approximation algorithms.
  • Multicommodity flows and disjoint paths.
  • Tree decompositions of graphs and  algorithmic applications of such decompositions.
  • Parametrized complexity.
  • NP-completeness proofs.
  • Chordal graphs.

Literature

See itslearning for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Spring

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 exam paper, along with selected topics from the course, forms the basis for the oral examination. The grade is based on an overall impression of the assignments and the oral examination. Censor will be able to view the answers to the assignments.

Reeksamen is an oral exam, which is graded according to the 7th grade and external examiner.

Indicative number of lessons

65 hours per semester

Teaching Method

At the faculty of science, teaching is organized after the three-phase model ie. intro, training and study phase.
  • The intro phase is 35 hours
  • The training phase 30 hours.
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.

Teacher responsible

Name E-mail Department
Jørgen Bang-Jensen jbj@imada.sdu.dk Algoritmer

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi)

Team at Educational Law & Registration

NAT

Offered in

Odense

Recommended course of study

Profile Education Semester Offer period

Transition rules

Transitional arrangements describe how a course replaces another course when changes are made to the course of study. 
If a transitional arrangement has been made for a course, it will be stated in the list. 
See transitional arrangements for all courses at the Faculty of Science.