Graduate Seminar on Discrete Optimization (S4C1)

Summer 2014


LP and SDP relaxations


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.


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

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


Prof. Dr. B. Korte,
Prof. Dr. J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. N. Hähnle,
Dr. U. Brenner