### Page Content

### to Navigation

## News

- (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

room | phone | e-mail | office hours | ||
---|---|---|---|---|---|

Lecturer | Prof. Dr. Martin Skutella | MA 521 | (030) 314-28641 | skutella | Tuesday 10-11 |

Lecturer | Dr. Britta Peis | MA 523 | (030) 314-27447 | peis | by appointment |

Student Assistant | Ágnes Cseh | MA 516 | cseh | Monday 10-11 |

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

## Schedule

Weekday | Hour | Room | |
---|---|---|---|

Lecture | Tuesday | 12:15 - 13:45 | MA 041 |

Lecture | Friday | 10:15 - 11:45 | MA 042 |

Exercise Session | Thursday | 12:15 - 13:45 | MA 650 |

Tutorial Session 1 | Monday | 12:15 - 13:45 | MA 545 |

Tutorial Session 2 | Tuesday | 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**

- Lecture 10/04/2012: slides, notes b/w, notes col (
**Advanced Linear Programming & Polyhedral Theory**: Fourier-Motzkin Elimination, Separating Hyperplane Theorem, Cones, Extreme Rays) - 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)
- 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)
- 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)
- Lecture 24/04/2012: slides, notes b/w, notes col (Dantzig-Wolfe Decomposition)
- Lecture 27/04/2012: slides, notes b/w, notes col (Interior Point Methods: Affine Scaling Algorithm)
- Lecture 04/05/2012: slides, notes b/w, notes col ( (Interior Point Methods: Potential Reduction Algorithm:)
- Lecture 08/05/2012: slides, notes col (
**Matchings**: Maximum Matching and Minimum Node Cover, Theorems of Kőnig, Hall, Berge, Tutte, Certicates for Maximum Matchings) - Lecture 11/05/2012: slides, notes 1, notes 2 (Blossom Shrinking Lemma, Edmonds' Matching Algorithm)
- Lecture 15/05/2012: slides, notes b/w, notes col (Minimum-Weight Perfect Matchings, Birkhoff's Theorem, Hungarian Algorithm)
- 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)
- Lecture 22/05/2012: slides, notes b/w, notes col (Maximum-Weight Matching Problem, Geometric Interpretation of the Dual LP, Goemans-Williamson Algorithm)
- Exercise 24/05/2012: slides (Minimum Weight Perfect Matching on General Graphs, example)
- Lecture 25/05/2012: slides, notes b/w, notes col (Postman Problem, T-Joins)
- Lecture 29/05/2012: slides, notes col (
**Integer Linear Programming**: Convex Hulls, Separating Hyperplanes, Faces and Vertices of a Polyhedron) - Lecture 31/05/2012: slides, notes col (Characterization of Polytopes, Min-Max Relations, Hoffman's Characterization of Integral Polytopes)
- Lecture 05/06/2012: slides, notes b/w (Sufficient Conditions for Integrality, Total Unimodularity: Polyhedra without Non-Negativity Constraints)
- Lecture 08/06/2012: slides, notes col (Node-Arc Incidence-Matrices, Network Matrices, Total Dual Integrality, Cutting Planes, Gomory-Chvatal Cutting Planes)
- Lecture 11/06/2012: slides, notes b/w (Cutting-Plane Proofs, Chvátal Rank, Cutting-Plane Algorithms)
- Lecture 15/06/2012: slides, notes col (
**The Traveling Salesperson Problem**: Heuristics, Triangle Inequality, Insertion Methods, Christofides' Heuristic) - Lecture 19/06/2012: slides, notes col (Christofides' Heuristic, Tour Improvements Methods, Lower Bounds, Linear Relaxation of TSP, Comb Inequalities)
- Lecture 22/06/2012: slides, notes col (Branch and Bound,
**Matroids**, Greedy algorithm) - Lecture 26/06/2012: slides, notes b/w, notes col (Matroids, bases, circuits, rank, rank quotient, greedy algorithm, polyhedral structure)
- Lecture 29/06/2012: slides, notes b/w (
**Matroid Intersection**) - Lecture 09/07/2012: slides, notes col (
**Approximation Algorithms**for Set Cover) - Lecture 1307/2012: slides, notes col (Primal-dual algorithm for feedback vertex set and lattice polyhedra)

## Homework

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