DM867: Combinatorial Optimization

Study Board of Science

Teaching language: Danish, but English if international students are enrolled
EKA: N340014102
Censorship: 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: 25-04-2019


Duration: 1 semester

Version: Approved - active

Comment

New course E18 (Autumn 2018)

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.
  • 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

See Blackboard for syllabus lists and additional literature references.

Examination regulations

Exam element a)

Timing

Autumn

Tests

Oral exam and an assignments handed-in during the course.

EKA

N340014102

Censorship

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.

Indicative number of lessons

70 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 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

Timetable

Administrative Unit

Institut for Matematik og Datalogi (datalogi, fiktiv)

Recommended course of study

Profile Programme Semester Period