# Computational Complexity - Research Seminar

## René Beier (MPI Informatik): *Improving the Separation Lemma*

May 24, 2006, 10:15 a.m.

E 1 3, Room 415

Given a binary optimization problem with a random linear constraint (coefficients are chosen at random or they are randomly perturbed), it is well known that the slack of the optimal solution with respect to this constraint has polynomial expected size.

Can this result be generalized to integer linear programs with bounded variable domain?