In this seminar we will discuss techniques for obtaining strongly polynomial algorithms for quite general classes of problems. We will cover recent breakthrough results by Lee, Sidford and Wong who gave improved weakly and strongly polynomial time algorithms based on convex programming for many classical problems in combinatorial optimization (such as submodular function minimization, matroid intersection and submodular flow). We will also see more classical and very powerful results due to Frank and Tardos that provide strongly polynomial algorithms for solving combinatorial LPs.

Number | Approval talk | Talk | Name | Topic | Mentoring |
---|---|---|---|---|---|

1 | 8.4. (Fr.), 14:15 | 18.4. | Tilmann Bihler | A fast approximation for maximum weight matroid intersection | S. Daboul |

2 | 11.4. | 25.4. | Rodion Permin | Diophantine Approximation | S. Daboul |

3 | 18.4. | 2.5. | Bento Natura | Combinatorial LPs | A. Hermann |

4 | 25.4. | 9.5. | Patrick Schnibben | Abstract Combinatorial LPs | A. Hermann |

5 | 2.5. | 23.5. | Daniel Wochnik | Fixed-Dimensional IPs | T. Silveira Salles |

6 | 9.5. | 30.5. | Khai Van Tran | Polymatroid Intersection I | M. Ahrens |

7 | 23.5. | 6.6. | Andrei Sterin | Polymatroid Intersection II | M. Ahrens |

8 | 30.5. | 13.6. | Vera Traub | Faster Cutting Plane Method | R. Scheifele |

9 | 6.6. | 20.6. | Berk Öcal | Convex and Semidefinite Programming | R. Scheifele |

10 | 13.6. | 27.6. | Andreas Haupt | Intersection of Convex Sets | D. Rotter |

11 | 20.6. | 4.7. | Lukas Polten | Weakly Polynomial Submodular Function Minimization | D. Rotter |

12 | 27.6. | 11.7. | Malte Grändorf | Strongly Polynomial Submodular Function Minimization I | P. Cremer |

13 | 4.7. | 18.7. | Falko Hegerfeld | Strongly Polynomial Submodular Function Minimization II | P. Cremer |

Talk given by A. Sidford and Y. Lee about their paper "A faster cutting plane method and its implications for combinatorial and convex optimization" (joint work with S. Wong). The paper is the source for the talks 8-13 in our seminar.

Every participant should have read in advance the chapters 4 and 14 of the book "Combinatorial Optimization: Theory and Algorithms" by B. Korte, J. Vygen (Fifth edition 2012).

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

Prof. Dr. J. Könemann,

Dr. U. Brenner