Research Institute for Discrete Mathematics

Exercise class for the course "Combinatorial Optimization"

Winter Term 2022/23

Tueday, 10:15-11:45 (Malte Schürks) or Friday, 14:15-15:45 (Meike Neuwohner, Stefan Rabenstein) in the lecture hall, Research Institute for Discrete Mathematics.

Exercise sets:

Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9 (Updated: fixed exercise 9.2)
Set 10
Set 11 (Updated: fixed exercises 11.2 (ii) and (iii))
Set 12
Bonus exercises

Programming exercise 1:

Exercise sheet
Example graph class
Example instances
- Note: The USA-road-d.* instances are very large and should be treated as "bonus" instances. It is not required to be able to solve these instances quickly, however your code should in theory be able to solve them given enough runtime.
Cardinalities of maximum matchings of the example instances
Solutions should be submitted by email to Malte Schürks

Programming exercise 2:

Exercise sheet
Example graph class, min-cost matching solver and instances
Solutions should be submitted by email to Malte Schürks

Solutions are submitted on Thursdays before the lecture.

Submissions typeset in LaTeX are welcome via email to the tutor, but the same deadline applies.

Solutions may be submitted in groups of up to three students.

There will be 2 or 3 programming exercises.

Students need to achieve both at least 50 % of the points in the theoretical exercises and at least 50 % of the points in the programming exercises.

It is recommended to register in the eCampus course for the lecture.

Main Tutor: Malte Schürks
Tutors: Meike Neuwohner, Stefan Rabenstein