Chapter 19 Randomized Rounding Without Solving the Linear Program

We introduce a new technique called oblivious rounding-a variant of randomized rounding that avoids the bottleneck of first solving the linear program. Avoiding this bottle-neck yields more efficient algorithms and brings probabilistic methods to bear on a new class of problems. We give obliv-ious rounding algorithms that approximately solve general packing and covering problems, including a parallel algo-rithm to find sparse strategies for matrix games