Combinatorial Optimization

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Adrian Bock

News & Log

Announcements and course topics will be posted here.

  • The announcement for the exam is online.
  • A sample exam is available here !
  • Exercise sheet 5 has been updated.
  • Exercise sheet 4 has been updated.
  • Note that the first exercise session will take place on September 27. The first exercise sheet will be avalaible for the first lecture and solutions to it for bonus must be handed in at the beginning of the exercise session on October 4.

 Log:

22.09.  Recap linear programming and duality

29.09. Randomized algorithm for finding a perfect matching, based on Schwartz-Zippel-lemma

06.10. TDI, weighted matching polytope

13.10. Matching polytope is TDI, begin Ellipsoid method

20.10. Ellipsoid method

27.10. Separation problem for Matching polytope: minimum odd cuts

03.11. Matroids: definition, Greedy algorithm

10.11. Matroids: Job Scheduling, Matching matroid

17.11. Matroid polytope, arborescences

24.11. Minimum cost r-arborescence, r-Cuts

01.12. Min-max-relation, P vs. NP

08.12. Polynomial transformations, 3-SAT, vertex-cover

15.12. Vertex cover: 2-apx, Steiner tree: NP-complete, 2-apx

22.12.

Description

This lecture will cover a selection of problems in Combinatorial Optimization. On this basis, the students will learn the relation between polyhedra and efficiency. This involves correctness proofs and objective is to enhance the mathematical modelling skills of the students to enable them to recognize and exploit combinatorial optimization problems in broader contexts.

Here is the course book description of the class.

Schedule

Lecture: Thursday 15:15 – 17:00 (MA A3 30); first lecture on September 22nd
Exercises: Tuesday 17:15 – 19:00 (MA A3 31); first session on September 27th

Grading

Your grade will be determined by a written final exam.

You can collect bonus points by handing in solutions to selected exercises from the assignment sheets. If you solve 50% or more of the exercises, the grade of your final exam will be improved by a half grade. If you solve 90% or more of the exercises, the grade of your final exam will be improved by a full grade.

Assignments

We will publish an assignment sheet with problems and practical exercises on this website every two weeks. You can work on the exercises, ask questions, and discuss problems during the exercise sessions.

You will have the opportunity to hand in written solutions for feedback. Correct solutions to selected “star” problems give bonus points. We will discuss solutions during the exercise sessions. Solutions can be submitted in groups of up to three people.

Notes on some of the previous exercises will also be posted below. However, they typically do not contain complete solutions and only give final results and/or a rough sketch of a viable solution approach.

Literature

  • Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag.
  • William J. Cook, Willian H. Cunningham, William R. Pulleyblank, A. Schriver, Combinatorial Optimization, Wiley-Interscience.