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 |

- 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,

Dr. N. Hähnle,

Dr. U. Brenner