Combinatorial Optimization

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Yuri Faenza

News & Log

The final exam will take place on 27.1 8h15-11h15 in room CM1.

As an example, you can find here a copy of the 2011 exam (NB: some of the topics covered in 2011 were different from those discussed this year). 

 

Topics covered during the course:

  • 19/09: Connector problem and minimum spanning tree problem
  • 26/09: Matroids: definition, greedy algorithm
  • 03/10: Matroid polytope ([2] (also for previous lectures))
  • 10/10: 2-approximation for the Steiner tree problem
  • 17/10: 4-approximation for single source rent or buy problem ([3], Sec. 12.2)
  • 24/10: r-rooted arborescences ([4], Sec. 4.9)
  • 31/10: Randomized algorithm for min cut ([2], Sec. 3.5.1)
  • 07/11: Maximum matching using the Schwartz-Zippel Lemma
  • 14/11: Gomory-Hu trees ([2], Sec. 3.5.2)
  • 21/11: 1/4 randomized and 1/3 deterministic approximation for the maximization of nonnegative submodular functions (see here)
  • 28/11: Maximization of nonnegative submodular functions under cardinality and matroid constraints (see here)
  • 05/12: The ellipsoid method for linear programming, with application to matching (see here, also for next lecture)
  • 12/12: Linear description of the matching polytope
  • 19/12: Solving matching with bit scaling

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 you can find out more about the course.

Schedule

Lecture: Thursday 17:15 – 19:00 (MA A1 10); 
Exercises: Tuesday 17:15 – 19:00 (MA A3 31); 

Grading

Your grade will be determined by a written final exam.

You can collect bonus points by handing in solutions to selected exercises (“star” exercise) from the assignment sheets. If you solve 90% or more of the exercises, the grade of your final exam will be improved by a full grade. If you solve x % of the exercises, with 50 <= x < 90, the grade of your final exam will be improved by 1/2 + (x-50)/80 points. If you solve less than 50% of the exercises, you will get no bonus.

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 also have the opportunity to discussion your solutions for feedback. You can submit solutions to selected “star” problems that will give bonus points. We will publish a sketch of the solutions online and if needed discuss them at the blackboard during the exercise sessions. Solutions can be submitted in groups of up to three people.

 

Literature

  1. Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag.
  2. William J. Cook, Willian H. Cunningham, William R. Pulleyblank, A. Schriver, Combinatorial Optimization, Wiley-Interscience.
  3. David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press (online version)
  4. Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley.