A Randomized Algorithm for Minimum Cuts
Andreas Klappenecker · 2012
A randomized algorithm is an algorithm that receives, in addition to its input, a stream of random bits which is used to make random choices. The random bits are assumed to be independent of the input. A salient feature is that repeated runs of a randomized algorithm with fixed input data will, in general, not produce the same result. You might be perplexed that such a lack of definiteness is desirable, but consider that this feature allows to transform deterministic algorithms with bad worst case behaviour into randomized algorithms that perform well with high probability on any input. I hope that the next example can convey that randomized algorithms are often simple and efficient.