Random Sampling and Randomized Rounding of Linear Programs
David P. Williamson, David B. Shmoys · Cambridge University Press eBooks · 2011
Sometimes it turns out to be useful to allow our algorithms to make random choices; that is, the algorithm can flip a coin, or flip a biased coin, or draw a value uniformly from a given interval. The performance guarantee of an approximation algorithm that makes random choices is then the expected value of the solution produced relative to the value of an optimal solution, where the expectation is taken over the random choices of the algorithm. At first this might seem like a weaker class of algorithm. In what sense is there a performance guarantee if it holds only in expectation? However, in most cases we will be able to show that randomized approximation algorithms can be derandomized : that is, we can use a certain algorithmic technique known as the method of conditional expectations to produce a deterministic version of the algorithm that has the same performance guarantee as the randomized version. Of what use then is randomization? It turns out that it is often much simpler to state and analyze the randomized version of the algorithm than to state and analyze the deterministic version that results from derandomization. Thus, randomization gains us simplicity in our algorithm design and analysis, while derandomization ensures that the performance guarantee can be obtained deterministically.