Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




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?