Prabhakar Raghavan and Clark D. Thompson

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-85-242

, 1985

http://www2.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},
    Year= {1985},
    Month= {May},
    Url= {http://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1985/5636.html
%F Raghavan:CSD-85-242