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).

Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Prof. Dr. J. Könemann,
Dr. U. Brenner