DM209: Combinatorial Optimization II (5 ECTS)

STADS: 15007801

Level
PhD course

Teaching period
The course is offered in the autumn semester.
2nd quarter

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
Ubegrænset deltagerantal. Kurset kører i 2. kvartal.

Prerequisites:
None

Academic preconditions:
Bachelor deegree in computer science or mathematics. knowledge about the topic of DM508 and DM515. It is an advantage, but not a demand, that the topics of Combinatorial Optimization I are known.

Course introduction
The purpose of this course and its predecessor Combinatorial Optimization I is to give the student a detailed knowledge of topics within combinatorial optimization. Several of the techniques and problems covered in the two courses have great pracitcal relevance. These connections to practical problems will be clarified in the course.

Expected learning outcome
At the end of the course the student should be able to

• Apply the theory and the algorithms from the course on concrete problem instances.
• Give an account of proofs within curriculum of the course.
• Give an account of algorithms and methods covered in the course and give the complexity of the algorithms.
• Apply methods, models and algorithmic ideas covered in the course.

Subject overview
Integrality of polyhedra, approximation algorithms, the knapsack and bin packing problems, Lagrange relaxation, multicommodity flows, network design, the TSP problem, Tree-decompositions and applications.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral examination, grades according to the Danish 7-point grading scale and external censorship.

Re-examination according to the rules approved by the Study Board.
The re-exam may differ from the ordinary exam.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger, 22 timer
Eksaminatorietimer, 14 timer
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.