Summer 2013
Semidefinite Programming and Approximation Algorithms
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.
Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Jun.Prof. Dr. S. Held,
Dr. U. Brenner