Combinatorial Optimization

Lecturer

Prof. Friedrich Eisenbrand

Assistant

Nicolai Hähnle

News & Log

  • Created a Doodle poll to check if there is a better time slot for the exercise sessions
  • Announcements and course topics will be posted here

LOG:

  • 23. Sept.: Recap Linear Programming, duality and polyhedra, proving optimality of Matchings
  • 30. Sept.: Integral polyhedra, TDI-systems
  • 7. Oct.: TDI-ness of Matching description
  • 14. Oct.: Half-Ball Lemma, Ellipsoid Method, Binary Search
  • 21. Oct.: Analysis of Ellipsoid Method for Matching, perfect matching Polytope
  • 28. Oct.: Submodularity of cuts, odd T-cut algorithm, Karger’s min-cut algorithm
  • 4. Nov.: Max Flow/ Min Cut and Edmonds Karp Analysis of Ford Fulkerson
  • 11. Nov.: Gomory Hu Trees, Definition and First Steps
  • 18. Nov.: Existence of G-H-Trees, Matroids: Definition Examples
  • 25. Nov.: Greedy Algorithm and Matroid Polytope
  • 02. Dec.: Proof of Matroid Polytope Theorem and Arborescences
  • 09. Dec.: P and NP, NP-completeness, Cook’s theorem
  • 16. Dec.: Reductions, Stable Set, Vertex Cover, Set Cover Approximation Algorithm for Set Cover

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.

Schedule

Lecture: Thursday 15:15 – 17:00 (MA A3 31); first lecture on September 23rd
Exercises: Monday 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.

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.