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?