# Combinatorial Optimization

### Lecturer

Prof. Friedrich Eisenbrand

Manuel  Aprile

### News & Log

• 21/09: Minimum spanning trees, Chapter 1.4 of Schrijver’s lecture notes
• 28/09: Maximum flow, Chapters 4.2, 4.3 of Schrijver’s lecture notes
• 05/10: Edmonds-Karp algorithm and circulations, Chapters 4.3, 4.5 of Schrijver’s lecture notes
• 19/10: Flow decomposition and negative cycles, Chapter 7.5 of the Course notes
• 26/10: Capacity scaling algorithm; Matchings and Tutte matrix
• 02/11: Edmonds’ blossom shrink algorithm, Chapter 5.2 of Schrijver’s lecture notes
• 09/11: Matroids and the greedy algorithm, Chapter 10.1 of Schrijver’s lecture notes
• 16/11: The Matroid Polytope; the Matching Polytope (1), Chapter 10.7 of Schrijver’s lecture notes
• 23/11: The Matching Polytope (2), Chapter 5.4 of Schrijver’s lecture notes
• 30/11: Matroid Intersection, Chapter 10.5 of Schrijver’s lecture notes
• 07/12: Matroid Intersection Polytope, Chapter 10.7 of Schrijver’s lecture notes
• 14/12: The separation problem and the Ellipsoid method, Chapter 8 of the Course notes
• 21/12: Equivalence between separation and optimization, Schrijver’s book

### Description

The guiding question of Combinatorial Optimization is: How do I efficiently select an optimal solution among a finite but very large set of alternatives? We will address the solution of this question in the context of classical discrete optimization problems.

Here you can find out more about the course.

### Schedule

Lecture: Wednesday 13:15 – 15:00 (MA A1 10);
Exercises: Friday 10:15 – 12: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 from the assignment sheets. If you score an average of 50% or more in the exercises, the grade of your final exam will be improved by a half grade. If you score an average of 90% or more, the grade of your final exam will be improved by a full grade. The bonus points will be awarded only to students who get a grade of at least 4 in the exam.

### Assignments

We will publish an assignment sheet with problems and practical exercises on this website every week. 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. You can submit the assignments in groups of maximum three students. Correct solutions to selected “star” problems give bonus points. The deadline is one week after the sheet is issued. More precisely, you can either leave your solutions in the box next to office MA C1 563 (be sure you put them in the correct box) or send them via email10:00on Friday, or hand them personally to the assistant before the exercise session starts.

We will discuss solutions during the exercise sessions. For any question about the exercises and the material, don’t hesitate to send an email or come during office hours on Tuesday, 2 pm.

### 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.
5. Alexander Schrijver, A Course in Combinatorial Optimization, Course Notes (online version)
6. Thomas Rothvoss, Discrete Optimization, Course Notes (online version)
7. Friedrich Eisenbrand, Discrete Optimization, Course Notes (online version)