Lecturer
Assistant
News & Log
16.09: The Edmonds-Karp maximum flow algorithm (section 7.4 from Discrete Optimization lecture notes)
23.09: Minimum cost network flows (section 7.5 from Discrete Optimization lecture notes)
30.09: Minimum cost network flows continued (section 7.5 from Discrete Optimization lecture notes)
07.10: The Ellipsoid Method (chapter 8 from Discrete Optimization lecture notes)
14.10: Minimum spanning trees and Matroids (sections 4.1 and 10.1 from these notes)
21.10: Matroid Optimization (following these notes)
28.10: Matroid Optimization continued (following these notes)
04.11 Matroid Intersection and the Separation Problem
11.11 Maximum cardinality matching (chapter 8 from these notes)
18.11 The matching polytope (section 6.3 from Discrete Optimization lecture notes)
25.11 P, NP, and NP-completeness (chapter 6 from these notes)
2.12 P, NP, and NP-completeness continued
9.12 FPTAS for the knapsack problem, Vertex cover
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 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 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. Exercises must be submitted individually. 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 mail by 10:00 on Friday, or hand them personally to the assistant before the exercise session starts.
We will discuss solutions during the exercise sessions.
Assignment 1 (Solutions)
Assignment 2 (Solutions)
Assignment 3 (Solutions)
Assignment 4 (Solutions)
Assignment 5 (Solutions)
Assignment 6 (Solutions)
Assignment 7 (Solutions)
Assignment 8 (Solutions)
Assignment 9 (Solutions)
Assignment 10 (Solutions)
Assignment 11 (Solutions)
Assignment 12 (Solutions)
Assignment 13 (Solutions)
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.
- David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms, Cambridge University Press (online version)
- Jon Kleinberg and Eva Tardos, Algorithm Design, Addison-Wesley.
- Alexander Schrijver, A Course in Combinatorial Optimization, Course Notes (online version)
- Thomas Rothvoss, Discrete Optimization, Course Notes (online version)
- Friedrich Eisenbrand, Discrete Optimization, Course Notes (online version)