In this seminar we will study discrete analogies of convex analysis for nonlinear discrete optimization, which can be considered as a generalization of matroid and submodular function theory. We will study the major theoretical results as well as the main applications of discrete convex analysis. Most topics are based on the book "Discrete Convex Analysis" by Kazuo Murota (SIAM, 2003). In addition, we cover the currently fastest algorithms for submodular function minimization, as well as recent applications of discrete convex analysis.

Talk | Approval Talk | Title | Student | Tutor |

13.04.2015 | 07.04.2015, 12:15 | M/M# Convex Functions (Sections 6.1-6.7) | Tom Mechandijski | Rudolf Scheifele |

20.04.2015 | 26.03.2015, 14:15 | L/L# Convex Functions (Sections 7.1-7.5) | Lukasz Segiet | Rudolf Scheifele |

27.04.2015 | 13.04.2015 | Convex Extensions and Polyhedral Convexity(Sections 6.10,6.11,7.7,7.8) | On Hei Solomon Lo | Jannik Silvanus |

04.05.2015 | 20.04.2015 | Conjugacy (Section 8.1) | Beni Egressy | Daniel Rotter |

11.05.2015 | 27.04.2015 | Duality (Section 8.2, 9.1.4) | Judith Brecklinghaus | Daniel Rotter |

18.05.2015 | 04.05.2015 | Nonlinear Networks (Sections 2.2 and 9.6) | Alexander Goeke | Michael Gester |

01.06.2015 | 11.05.2015 | Minimizing M-convex and L-convex functions (Sections 10.1+10.3) | Lukas Miething | Michael Gester |

08.06.2015 | 18.05.2015 | M-Convex Submodular Flow Problems(Sections 9.2+9.3) | Alexander Platz | Pascal Cremer |

15.06.2015 | 01.06.2015 | Minimizing M-convex submodular flows (Section 10.4) | Maximilian Janke | Pascal Cremer |

22.06.2015 | 08.06.2015 | A simple combinatorial algorithm for submodular function minimization | Wolfgang Leyrer | Ulrike Schorr |

29.06.2015 | 15.06.2015 | A faster strongly polynomial time algorithm for submodular function minimization, | Mirko Wilde | Philipp Ochsendorf |

06.07.2015 | 22.06.2015 | A two-sided discrete-concave market with bounded side payments: An approach by discrete convex analysis. | Xianghui Zhong | Niko Klewinghaus |

- 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. N. Hähnle,

Dr. U. Brenner