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 | 28.5. (10:00 s.t.) |
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 |
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner