DM209: Combinatorial Optimization II (5 ECTS)

STADS: 15007801

Level
PhD course

Teaching period
The course is offered in the autumn semester.
Offered according to needs.

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 3. kvartal.

Prerequisites:
None

Academic preconditions:
Bachelor's degree in computer science or mathematics. Knowledge about the topics of DM508 Algorithms and Complexity and DM515 Introduction to linear and integer programming.

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, fixed parameter algorithms, Lagrange relaxation, multicommodity flows and disjoint paths in graphs, network design, Tree-decompositions and applications, chordal graphs, NP-completeness.

Literature

• Meddeles ved kursets start.

Syllabus
See syllabus.

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.