TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)Discrete Optimization (ADM II)

COGA 5-Wheel

Page Content

to Navigation

Discrete Optimization (ADM II)


  • (2012/07/29)  All ADM II slides can be found here: https://dl.dropbox.com/u/22668316/ADM2.zip,
    ADM I lecture notes: https://dl.dropbox.com/u/22668316/adm1.pdf
  • (2012/06/28) If you have not checked your data on the students' list and added your course of studies (Studiengang), please send an e-mail to Ágnes with the following details: name, matrikulation number, course of studies. Without this you may have difficulties with getting the Schein.
  • (2012/06/28) Oral exam dates are July 30 & 31  and September 24-26.
  • (2012/06/26) There is no class on Tuesday, July 3, and Friday, July 6 and no exercise session on Thursday, July 5. Tutorial sessions are held both on Monday, July 2 and on Tuesday, July 3. These are the last tutorials in this semester.
  • (2012/06/26) The right side of the first inequality in Exercise 62 is |S|-1 instead of |V|-1.
  • (2012/05/01) There is no tutorial session on 7 May (Monday). Instead, a tutorial session is given on 9 May (Wednesday), 12:15-13:45 in MA 212.
  • (2012/04/19) There are no tutorial sessions in the week 30 April - 6 May. You can reach Ágnes only via e-mail.
  • (2012/04/19) Due to the postponed tutorial sessions, the deadline for the second set of exercises is Friday, 27 April. You can hand in your solutions either before the lecture or later in the secretary office MA 501.
  • (2012/04/12) On April 23 and on April 24 there are no tutorial sessions. Instead, tutorial sessions are given on April 26, 14:15-15:45 and 16:00-17:30 in MA 212 (BMS seminar room).
  • (2012/04/12) The tutorial session on Monday is held in German, the one on Tuesday is held in English.
  • (2012/04/10) The first exercise session takes place on April 19 (in MA 650).
  • Welcome! This is the webpage of the course ADM II taught by Dr. Britta Peis and Prof. Martin Skutella. Please be aware that the contents of the lectures ADM I + II have changed according to this description.

Contact Information

office hours
Prof. Dr. Martin Skutella
MA 521
(030) 314-28641

Tuesday 10-11
Dr. Britta Peis
MA 523
(030) 314-27447

by appointment
Student Assistant
Ágnes Cseh
MA 516

Monday 10-11

Complete the e-mail addresses by adding 'at'math.tu-berlin.de or click on the link to leave a message.


12:15 - 13:45
MA 041
10:15 - 11:45
MA 042
Exercise Session
12:15 - 13:45
MA 650
Tutorial Session 1
12:15 - 13:45
MA 545
Tutorial Session 2
14:15 - 15:45
MA 850

Slides and Lecture Notes

All slides can be found here: https://dl.dropbox.com/u/22668316/ADM2.zip,
ADM I lecture notes: https://dl.dropbox.com/u/22668316/adm1.pdf



  1. Lecture 10/04/2012: slides, notes b/w, notes col (Advanced Linear Programming & Polyhedral Theory: Fourier-Motzkin Elimination, Separating Hyperplane Theorem, Cones, Extreme Rays)
  2. Lecture 13/04/2012: slides, notes b/w, notes col (Characterization of Unbounded LPs, Resolution Theorem, Representation of Polyhedra, Local Sensitivity Analysis: Adding New Variable/Inequality)
  3. Lecture 17/04/2012: slides, notes b/w, notes col (Local Sensitivity Analysis: Adding New Equation/Changing Right-Hand Side/Cost Vector/Column of A, Global Dependence on the Right-Hand Side/on the Cost Vector, Set of all Dual Optimal Solutions)
  4. Lecture 20/04/2012: slides, notes b/w, notes col (Parametric Programming, Large-Scale Linear Programming: Delayed Column Generation, Pricing Problem and Dual Separation Problem, Cutting Plane Methods)
  5. Lecture 24/04/2012: slides, notes b/w, notes col (Dantzig-Wolfe Decomposition)
  6. Lecture 27/04/2012: slides, notes b/w, notes col (Interior Point Methods: Affine Scaling Algorithm)
  7. Lecture 04/05/2012: slides, notes b/w, notes col ( (Interior Point Methods:  Potential Reduction Algorithm:)
  8. Lecture 08/05/2012: slides, notes col (Matchings: Maximum Matching and Minimum Node Cover, Theorems of Kőnig, Hall, Berge, Tutte, Certi cates for Maximum Matchings)
  9. Lecture 11/05/2012: slides, notes 1, notes 2 (Blossom Shrinking Lemma, Edmonds' Matching Algorithm)
  10. Lecture 15/05/2012: slides, notes b/w, notes col (Minimum-Weight Perfect Matchings, Birkho ff's Theorem, Hungarian Algorithm)
  11. Lecture 18/05/2012: slides, notes b/w, notes col (Strengthened LP for General Graphs and its Dual, Matching Polytope Theorem, Blossom Algorithm for Minimum-Weight Perfect Matching, Optimal Dual Solutions of Matching Problems)
  12. Lecture 22/05/2012: slides, notes b/w, notes col (Maximum-Weight Matching Problem, Geometric Interpretation of the Dual LP, Goemans-Williamson Algorithm)
  13. Exercise 24/05/2012: slides (Minimum Weight Perfect Matching on General Graphs, example)
  14. Lecture 25/05/2012: slides, notes b/w, notes col (Postman Problem, T-Joins)
  15. Lecture 29/05/2012: slides, notes col (Integer Linear Programming: Convex Hulls, Separating Hyperplanes, Faces and Vertices of a Polyhedron)
  16. Lecture 31/05/2012: slides, notes col (Characterization of Polytopes, Min-Max Relations, Hoff man's Characterization of Integral Polytopes)
  17. Lecture 05/06/2012: slides, notes b/w (Sufficient Conditions for Integrality, Total Unimodularity: Polyhedra without Non-Negativity Constraints)
  18. Lecture 08/06/2012: slides, notes col (Node-Arc Incidence-Matrices, Network Matrices, Total Dual Integrality, Cutting Planes, Gomory-Chvatal Cutting Planes)
  19. Lecture 11/06/2012: slides, notes b/w (Cutting-Plane Proofs, Chvátal Rank, Cutting-Plane Algorithms)
  20. Lecture 15/06/2012: slides, notes col (The Traveling Salesperson Problem: Heuristics, Triangle Inequality, Insertion Methods, Christo fides' Heuristic)
  21. Lecture 19/06/2012: slides, notes col (Christofi des' Heuristic, Tour Improvements Methods, Lower Bounds, Linear Relaxation of TSP, Comb Inequalities)
  22. Lecture 22/06/2012: slides, notes col (Branch and Bound, Matroids, Greedy algorithm)
  23. Lecture 26/06/2012: slides, notes b/w, notes col (Matroids, bases, circuits, rank, rank quotient, greedy algorithm, polyhedral structure)
  24. Lecture 29/06/2012: slides, notes b/w (Matroid Intersection)
  25. Lecture 09/07/2012: slides, notes col (Approximation Algorithms for Set Cover)
  26. Lecture 1307/2012: slides, notes col (Primal-dual algorithm for feedback vertex set and lattice polyhedra)


  1. first set of exercises (due-date: April 19)
  2. second set of exercises (due-date: Friday, April 27)
  3. third set of exercises (due-date: May 3)
  4. fourth set of exercises (due-date: May 18)
  5. fifth set of exercises (due-date: May 24)
  6. sixth set of exercises (due-date: May 31)
  7. seventh set of exercises (due-date: June 7)
  8. eighth set of exercises (due-date: June 14)
  9. ninth set of exercises (due-date: June 21)
  10. tenth set of exercises (due-date: June 28)
  11. eleventh set of exercises (due-date: July 5)

Homework results of each group


Quick Access

Schnellnavigation zur Seite über Nummerneingabe