Graduate Seminar on Discrete Optimization

Graduate Seminar on Discrete Optimization (S4C1)

Summer 2016

Advanced Strongly Polynomial Algorithms in Combinatorial Optimization

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.

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

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