We study the relation between a class of 0–1 integer linear programs and their rational relaxations. We give a randomized
algorithm for transforming an optimal solution of a relaxed problem into a provably good solution for the 0–1 problem. Our
technique can be a of extended to provide bounds on the disparity between the rational and 0–1 optima for a given problem
instance.
AMS subject classification 90 C 10
This work was supported by Semiconductor Research Corporation grant SRC 82-11-008 and an IBM Doctoral Fellowship.