Prabhakar Raghavan and Clark D. Thompson

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-85-242
May 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},
    Institution = {EECS Department, University of California, Berkeley},
    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