Graduate Seminar on Discrete Optimization

Graduate Seminar on Discrete Optimization (S4C1)

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

Number	Approval talk	Talk	Name	Topic	Mentoring
1	15.4.	29.4. (14:15 - 15:45)	Maxime Wegesin	Introduction	Michael Gester
2	22.4.	6.5.	Friedrich Saas	Approximating Max-Cut and MAX-SAT	Michael Gester
3	29.4.	13.5.	Nils Hoppmann	Optimality of the Hyperplane Rounding	Ulrike Suhl
4	6.5.	27.5.	Rasmus Schroeder	Approximate Graph Coloring	Jan Schneider
5	13.5.	3.6.	Christoph Matzke	Approximating MAX-3-SAT	Jan Schneider
6	27.5.	10.6.	Markus Ahrens	O(log^½ n) Approximation for Sparsest Cut	Daniel Rotter
7	3.6.	17.6.	Daniel Romen	Approximating CSPs	Philipp Ochsendorf
8	10.6.	24.6.	Eva-Maria Christiana Hols	Faster SDP algorithms	Niko Klewinghaus
9	17.6.	1.7.	Sophie Spirkl	Almost Linear Time Optimal Approximations for CSP	Ulrike Suhl

Knowledge of the following two papers is assumed:

L. Lovász: Semidefinite Programs and Combinatorial Optimization. In: Reed, Sales (Eds.), Recent Advances in Algorithms and Combinatorics (2003), 137-194.
M.X. Goemans: Semidefinite Programming and Combinatorial Optimization. Documenta Mathematica (1998), 657-666.

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.