Home > Research Groups > Algorithms and Complexity > Teaching > Combinatorial Optimization

Combinatorial Optimization

The course is held in English.

Overview

This course gives an introduction to combinatorial optimization. Algorithmic approaches and methods are presented and analyzed, and various combinatorial optimization problems are considered. Topics of the course include e.g. matchings, network flows and linear programming.

Lecturer

Lecture and tuturial are held by Marten Maack.

Homework Assignments

Weekly assignments are due on Tuesdays and must be submitted online in PANDA.

Dates and Locations

  •   Lecture: Monday, 11-14, F 1.110. Starting on 11.10.2021 and ending on 31.1.2022. Exceptions: No lecture on 1.11., 27.12, and 3.1. (holidays). On November 30 the lecture will be held in room F 0.231.
  • Tuturial: Tuesday, 11-13, F 2.211. Starting on 12.10.2021 and ending on 1.2.2022. Exceptions: No Tutorial on 28.12 and 4.1. (holidays).

Examination

  • Oral examination that will cover the lecture as well as the tutorials and homework exercises.
  • Prerequisite for admission to the exam (Studienleistung): At least 40% of the available points from the homework assignments.
  • Bonus system: If you participate actively in the tutorials (e.g. presentation of own solutions), you can improve your grade as follows: A minimum of 50% of the points for the homework improves the grade by 1/3 grade point, and a minimum of 75% of the points for the homework improves the grade by 2/3 grade points. An improvement of the grade 5 is not possible. Bonus points from earlier lectures cannot be credited.
  • Dates and Locations have not yet been set.

Material

Lecture material will be published in PANDA. Examples of helpful supporting literature include:

  • C. Papadimitriou and K. Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Courier Corporation, 1998.
  • B. Korte, J. Vygen: Combinatorial optimization: theory and algorithms. Springer-Verlag Berlin Heidelberg, 2009.
  • A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag Berlin Heidelberg, 2003.
  • C. Moore and S. Mertens: The Nature of Computation. Oxford University Press, 2011.