Lecturer
Assistant
Objectives
Combinatorial optimization is a young mathematical discipline at the interplay of mathematics and computer science. Very roughly, it deals with the problem of making optimal choices in huge discrete sets of alternatives. The goal is to design and analyze efficient algorithms to solve such combinatorial optimization problems and to be able to certify the optimality of your solutions. A very successful and appealing approach which has gained a lot of importance is the polyhedral method, which applies techniques from linear and integer programming. In this course will cover an introduction to the polyhedral approach and a selection of individual combinatorial optimization problems and their solutions.
Topics
Lattices, Hermite normal forms and shortest vectors
Branchings and spanning trees
Cuts and Gomory–Hu trees
Strongly polynomial algorithms
Approximation algorithms
Grading
The final grade is determined from the grades of the midterm (30%) and final exam (70%) respectively. Both exams are written exams of 120 min.
Schedule
Lectures: Wednesday 14:15-16:00, MAA330
(First Lecture: September 17)
Exercise sessions: Monday 17:15-19:00, MAA330
(First Exercise session: September 29)
Midterm exam: November 12 (during the lecture)
Final exam: TBA (in January?)
Software
During this course a small numer of real-world problems has to be modeled and solved with software tools. We will provide corresponding links here, as we proceed.
Textbooks
[KV08] Bernhard Korte and Jens Vygen. Combinatorial Optimization: Theory and Algorithms, 4th edition, vol. 21 of Algorithms and Combinatorics. Springer-Verlag, 2008.
[Sch03] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency (three volumes), vol. 24 of Algorithms and Combinatorics. Springer-Verlag, 2003.
[Vaz01] Vijay V. Vazirani. Approximation Algorithms, 1st edition, 2nd printing. Springer-Verlag, 2001.
Assignments
There is one assigmnet handout every 2 weeks. Each assignment is discussed two weeks after it is distributed. The exercise session between those dedicted to the detailed discussion of the assignment can be used by the student to ask questions to the assistant and to work together on the assignment in groups.
Additional material
Lecture notes on network flows
Logbook
- September 17: Recap linear programming and duality
- September 24: Proof of strong duality using Fourier-Motzkin elimination; introduction to matchings
- October 1: Tutte Matrix, determinant is 0 iff G has no perfect matching
- October 8: Schwartz Zippel Theorem, Randomized algorithm for matching
- October 15: Randomized Mincut Algorithm, Randomized primality test
- October 22: Polyhedra, Minkowski-Weil Theorem (writeup)
- October 30: Faces of polyhedra
- November 5: Facets and minimal faces; integer polyhedra
- November 12: Midterm
- November 19: Integral polyhedra, total unimodularity, bipartite matching
- November 27: Proof of the matching polytope theorem (writeup)
- December 03: Network flows (writeup)
- December 10: Minimum Cost Network Flows, negative cycle optimimality criterion
- December 17: Bit-Scaling for min cost network flows