 | This article may be confusing or unclear to readers. (May 2010) |
In computer science and operations research, randomized rounding[1] is a widely used approach for designing and analyzing approximation algorithms.[2][3]
Many combinatorial optimization problems are computationally intractable to solve exactly (to optimality). For such problems, randomized rounding can be used to design fast (polynomial time) approximation algorithms—that is, algorithms that are guaranteed to return an approximately optimal solution given any input.
The basic idea of randomized rounding is to convert an optimal solution of a relaxation of the problem into an approximately-optimal solution to the original problem. The resulting algorithm is usually analyzed using the probabilistic method.
- ^ Raghavan, Prabhakar; Tompson, Clark D. (1987), "Randomized rounding: A technique for provably good algorithms and algorithmic proofs", Combinatorica, 7 (4): 365–374, doi:10.1007/BF02579324, S2CID 5749936.
- ^ Motwani, Rajeev; Raghavan, Prabhakar (1995-08-25). Randomized algorithms. Cambridge University Press. ISBN 978-0-521-47465-8.
- ^ Vazirani, Vijay (2002-12-05). Approximation algorithms. Springer Verlag. ISBN 978-3-540-65367-7.