Graduate Seminar on Discrete Optimization

Graduate Seminar on Discrete Optimization (S4C1)

Summer 2015

Submodularity and Discrete Convexity

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.

Class hours: Mondays 14:15-15:45. Approval talks: 12:15-13:45

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