Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs
Prabhakar Raghavan and Clark D. Thompson
EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-85-242
May 1985
http://www.eecs.berkeley.edu/Pubs/TechRpts/1985/CSD-85-242.pdf
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.
BibTeX citation:
@techreport{Raghavan:CSD-85-242,
Author = {Raghavan, Prabhakar and Thompson, Clark D.},
Title = {Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs},
Institution = {EECS Department, University of California, Berkeley},
Year = {1985},
Month = {May},
URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1985/5636.html},
Number = {UCB/CSD-85-242},
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.}
}
EndNote citation:
%0 Report %A Raghavan, Prabhakar %A Thompson, Clark D. %T Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs %I EECS Department, University of California, Berkeley %D 1985 %@ UCB/CSD-85-242 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1985/5636.html %F Raghavan:CSD-85-242