Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs
Thompson, Clark D.
Technical Report Identifier: CSD-85-242
May 29, 1985
Abstract: We study the relation between a class of 0-1 integer linear programs and their rational relaxations. We show that the rational optimum to a problem instance can be used to construct a provably good 0-1 solution by means of a randomized algorithm. Our technique can be extended to provide bounds on the disparity between the rational and 0-1 optima for a given problem instance.