Linear programming relaxations are a powerful tool for solving and approximating combinatorial optimization problems. Much attention has been paid to methods that "automatically" strengthen a linear programming relaxation of a 0-1 integer program by adding variables and constraints in a systematic way, with the goal of obtaining better approximations for NP-hard problems. We will discuss recent research that exhibits both the strengths and the limitations of such methods.
Here is a list of topics for the seminar.
| Number | Approval talk | Talk | Name | Topic | Mentoring |
|---|---|---|---|---|---|
| 1 | 24.3. | 7.4. | Friedrich Saas | Cones of Matrices and Set-Functions and 0-1 Optimization | J. Silvanus |
| 2 | 31.3. | 14.4. | Eva-Lotta Meyer | Comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre Relaxations for 0-1 Programming | U. Schorr |
| 3 | 7.4. | 28.4. | Ines Exner | Integrality Gaps of Linear and Semi-definite Programming Relaxations for Knapsack | P. Ochsendorf |
| 4 | 14.4. | 5.5. | Frieder Smolny The talk is cancelled. | Understanding Set Cover: Sub-Exponential Time Approximations and Lift-and-Projext Methods | P. Ochsendorf |
| 5 | 28.4. | 12.5. | Nicolas Kämmerling | Directed Steiner Tree and the Lasserre Hierarchy | D. Rotter |
| 6 | 5.5. | 19.5. | Lukas Räderscheidt | How to Sell Hyperedges: The Hypermatching Assignment Problem | D. Rotter |
| 7 | 12.5. | 26.5. | Felizia Reinsch | Sherali-Adams Relaxations for the Matching Polytope | N. Klewinghaus |
| 8 | 19.5. | 2.6. | Mirko Wilde | Integrality Gaps for Sherali-Adams Relaxations | J. Silvanus |
| 9 | 26.5. | 16.6. | Siad Daboul | Linear Level Lasserre Lower Bounds for Certain k-CSPs | J. Schneider |
| 10 | 2.6. | 30.6. | Christoph Hunkenschröder | Approximate Constraint Satisfactions Requires Large LP Relaxations | N. Hähnle |
| 11 | 16.6. | 7.7. | Pietro Saccardi | Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations | U. Schorr |
| 12 | 30.6. | 14.7. | Philipp Weiß | Rounding Semidefinite Programming Hierarchies via Global Correlation | N. Hähnle |