Graduate Seminar on Discrete Optimization (S4C1)

Summer 2019


Matroid Parity

The matroid parity problem generalizes both non-bipartite matching and matroid intersection. In general there is no polynomial-time algorithm. However, if the matroid is representable, Lovász found a min-max formula and a polynomial-time algorithm for the unweighted problem. For the weighted problem a polynomial-time algorithm was found only recently. A main part of our seminar presents the recent paper by Iwata and Kobayashi.
Class hours: Mondays 14:15-15:45. Approval talks: 16:15-17:45

List of talks with references
Number Approval talk Talk Name Topic Mentoring
1 26.3. (13:15)
1.4. Koen van Greevenbroek The matroid matching problem Vera Traub
2 26.3. (15:15)
8.4. Janina Vogl A min-max formula for maximum size matroid matching Anna Hermann
3 1.4.
15.4. Matthias Kaul Linear matroid matching algorithm Anna Hermann
4 8.4.
29.4. Paul Timme Approximation algorithms Niko Klewinghaus
5 15.4.
6.5. Oliver Kiss LP relaxations Niko Klewinghaus
6 29.4.
13.5. Anna Köhne Weighted linear matroid parity algorithm: blossoms and dual feasibility Tilmann Bihler
7 6.5.
27.5. Mirko Speth Weighted linear matroid parity algorithm: optimality Tilmann Bihler
8 13.5.
3.6. Meike Neuwohner Weighted linear matroid parity algorithm: finding an augmenting path (I) Rudi Scheifele
9 27.5.
17.6. Jannis Blauth Weighted linear matroid parity algorithm: finding an augmenting path (II) Benjamin Klotz
10 3.6.
24.6. Claas Latta Weighted linear matroid parity algorithm: updating dual variables Pietro Saccardi
11 17.6.
1.7. Niklas Schlomberg Weighted linear matroid parity algorithm: augmentation Pietro Saccardi
12 24.6.
8.7. Maximilian Gläser Complexity of weighted linear matroid parity algorithm and aplications Vera Traub

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner