# 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