UC BERKELEY
EECS technical reports
TECHNICAL REPORTS


CSD-85-242.pdf
Oskicat catalog record
Conditions of Use

Archive Home Page

Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs

Authors:
Raghavan, Prabhakar
Thompson, Clark D.
Technical Report Identifier: CSD-85-242
May 29, 1985
CSD-85-242.pdf

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.